4 最短路径 10题
sy386: 最短距离 简单
https://sunnywhy.com/sfbj/10/4/386
现有一个共n个顶点（代表城市）、m条边（代表道路）的无向图（假设顶点编号为从0到n-1），每条边有各自的边权，代表两个城市之间的距离。求从s号城市出发到达t号城市的最短距离。
输入
第一行四个整数n、m、s、t（
接下来m行，每行三个整数u、v、w（
输出
输出一个整数，表示最短距离。如果无法到达，那么输出-1。
样例1
输入
6 6 0 2
0 1 2
0 2 5
0 3 1
2 3 2
1 2 1
4 5 1输出
3解释
对应的无向图如下图所示。
共有3条从0号顶点到2号顶点的路径：
0->3->2：距离为3；0->2：距离为5；0->1->2：距离为3。
因此最短距离为3。
样例2
输入
6 6 0 5
0 1 2
0 2 5
0 3 1
2 3 2
1 2 1
4 5 1输出
-1解释
和第一个样例相同的图，终点换成了5号顶点，显然从0号无法到达5号。
需要找到从给定的起始城市到目标城市的最短距离。可以使用Dijkstra算法来解决这个问题。Dijkstra算法是一种用于在图中找到最短路径的算法。它从起始节点开始，然后逐步扩展到所有可达的节点，每次选择当前最短的路径进行扩展。
以下是使用 Python 实现 Dijkstra 算法来解决这个问题的示例代码：
import heapq
def dijkstra(n, edges, s, t):
graph = [[] for _ in range(n)]
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w))
pq = [(0, s)] # (distance, node)
visited = set()
distances = [float('inf')] * n
distances[s] = 0
while pq:
dist, node = heapq.heappop(pq)
if node == t:
return dist
if node in visited:
continue
visited.add(node)
for neighbor, weight in graph[node]:
if neighbor not in visited:
new_dist = dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return -1
# Read input
n, m, s, t = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]
# Solve the problem and print the result
result = dijkstra(n, edges, s, t)
print(result)这段代码实现了 Dijkstra 算法来求解从起点到终点的最短路径。首先构建了一个图，然后使用优先队列来选择下一个要探索的节点，并在探索过程中更新最短距离。最后返回从起点到终点的最短距离。
这个版本的Dijkstra算法使用了一个集合visited来记录已经访问过的节点，这样可以避免对同一个节点的重复处理。当我们从优先队列中取出一个节点时，如果这个节点已经在visited集合中，那么我们就跳过这个节点，处理下一个节点。这样可以提高算法的效率。
此外，这个版本的Dijkstra算法还在找到目标节点t时就立即返回结果，而不是等到遍历完所有节点。这是因为Dijkstra算法保证了每次从优先队列中取出的节点就是当前距离最短的节点，所以当我们找到目标节点t时，就已经找到了从起始节点s到t的最短路径，无需再继续搜索。
这个版本的Dijkstra算法的时间复杂度仍然是O((V+E)logV)，其中V是顶点数，E是边数。这是因为每个节点最多会被加入到优先队列中一次（当找到一条更短的路径时），并且每条边都会被处理一次（在遍历节点的邻居时）。优先队列的插入和删除操作的时间复杂度都是O(logV)，所以总的时间复杂度是O((V+E)logV)。
Dijkstra 算法是一种经典的图算法，它综合运用了多种技术，包括邻接表、集合、优先队列（堆）、贪心算法和动态规划的思想。例题：最短距离，https://sunnywhy.com/sfbj/10/4/386
- 邻接表：Dijkstra 算法通常使用邻接表来表示图的结构，这样可以高效地存储图中的节点和边。
- 集合：在算法中需要跟踪已经访问过的节点，以避免重复访问，这一般使用集合（或哈希集合）来实现。
- 优先队列（堆）：Dijkstra 算法中需要选择下一个要探索的节点，通常使用优先队列（堆）来维护当前候选节点的集合，并确保每次都能快速找到距离起点最近的节点。
- 贪心算法：Dijkstra 算法每次选择距离起点最近的节点作为下一个要探索的节点，这是一种贪心策略，即每次做出局部最优的选择，期望最终能达到全局最优。
- 动态规划：Dijkstra 算法通过不断地更新节点的最短距离来逐步得到从起点到各个节点的最短路径，这是一种动态规划的思想，即将原问题拆解成若干子问题，并以最优子结构来解决。
综合运用这些技术，Dijkstra 算法能够高效地求解单源最短路径问题，对于解决许多实际问题具有重要意义。
第2种写法，没有用set记录访问过的结点。
import heapq
def dijkstra(n, s, t, edges):
graph = [[] for _ in range(n)]
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w))
distance = [float('inf')] * n
distance[s] = 0
queue = [(0, s)]
while queue:
dist, node = heapq.heappop(queue)
if dist != distance[node]:
continue
for neighbor, weight in graph[node]:
if distance[node] + weight < distance[neighbor]:
distance[neighbor] = distance[node] + weight
heapq.heappush(queue, (distance[neighbor], neighbor))
return distance[t] if distance[t] != float('inf') else -1
# 接收数据
n, m, s, t = map(int, input().split())
edges = []
for _ in range(m):
u, v, w = map(int, input().split())
edges.append((u, v, w))
# 调用函数
min_distance = dijkstra(n, s, t, edges)
print(min_distance)第15行的判断if dist != distance[node]: continue的作用是跳过已经找到更短路径的节点。
在Dijkstra算法中，我们使用优先队列（在Python中是heapq）来存储待处理的节点，每次从队列中取出当前距离最短的节点进行处理。但是在处理过程中，有可能会多次将同一个节点加入到队列中，因为我们可能会通过不同的路径到达同一个节点，每次到达时都会将其加入到队列中。
因此，当我们从队列中取出一个节点时，需要判断这个节点当前的最短距离是否与队列中存储的距离相同。如果不同，说明这个节点在队列中等待处理的时候，已经有了一条更短的路径，所以我们可以跳过这个节点，处理下一个节点。
sy387: 最短距离-多终点 简单
https://sunnywhy.com/sfbj/10/4/387
现有一个共n个顶点（代表城市）、m条边（代表道路）的无向图（假设顶点编号为从0到n-1），每条边有各自的边权，代表两个城市之间的距离。求从s号城市出发到达其他每个城市的最短距离。
输入
第一行三个整数n、m、s（
接下来m行，每行三个整数u、v、w（
输出
在一行中输出个整数，依次表示到达编号从0到n-1的顶点的最短距离。如果无法到达，那么输出-1。整数之间用空格隔开，行末不允许有多余的空格。
样例1
输入
6 6 0
0 1 2
0 2 5
0 3 1
2 3 2
1 2 1
4 5 1输出
0 2 3 1 -1 -1解释
对应的无向图如下图所示。最短路径：
0号顶点：直接到达，距离为0；
1号顶点：0->1，距离为2；
2号顶点：0->1->2和0->3->2，距离为3；
3号顶点：0->3，距离为1；
4号顶点：无法到达；
5号顶点：无法到达。
import heapq
def dijkstra(n, edges, s):
graph = [[] for _ in range(n)]
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w))
pq = [(0, s)] # (distance, node)
visited = set()
distances = [float('inf')] * n
distances[s] = 0
while pq:
dist, node = heapq.heappop(pq)
if node in visited:
continue
visited.add(node)
for neighbor, weight in graph[node]:
new_dist = dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return distances
# Read input
n, m, s = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]
# Solve the problem
result = dijkstra(n, edges, s)
# Output the result
print(' '.join(map(lambda x: str(x) if x != float('inf') else '-1', result)))sy388: 最短距离-多边权 简单
https://sunnywhy.com/sfbj/10/4/386
现有一个共个顶点（代表城市）、条边（代表道路）的无向图（假设顶点编号为从0到n-1），每条边有两种边权，分别代表两个城市之间的距离和花费。求从号城市出发到达号城市的最短距离，并在达到最短距离的路径中计算最少花费。
输入
第一行四个整数n、m、s、t（
接下来m行，每行四个整数u、v、w1、w2（
输出
输出两个整数，代表最短距离与最少花费。
数据保证最短路径一定存在。
样例1
输入
4 5 0 2
0 1 2 1
0 2 5 1
0 3 1 2
1 2 1 6
3 2 2 3输出
3 5解释
对应的无向图如下图所示，其中边上的第一个数字为边权距离，第二个数字为边权花费。
共有3条从0号顶点到2号顶点的路径：
0->3->2：距离为3，花费为5；0->2：距离为5，花费为1；0->1->2：距离为3，花费为7。
因此最短距离为3，最短路径有2条，在这2条最短路径中的最少花费是5。
import heapq
def dijkstra(n, edges, s, t):
graph = [[] for _ in range(n)]
for u, v, d, c in edges:
graph[u].append((v, d, c))
graph[v].append((u, d, c))
pq = [(0, 0, s)] # (distance, cost, node)
visited = set()
distances = [(float('inf'), float('inf'))] * n
distances[s] = (0, 0)
while pq:
dist, cost, node = heapq.heappop(pq)
if node == t:
return dist, cost
if node in visited:
continue
visited.add(node)
for neighbor, d, c in graph[node]:
new_dist = dist + d
new_cost = cost + c
if new_dist < distances[neighbor][0] or (new_dist == distances[neighbor][0] and new_cost < distances[neighbor][1]):
distances[neighbor] = (new_dist, new_cost)
heapq.heappush(pq, (new_dist, new_cost, neighbor))
# Read input
n, m, s, t = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]
# Solve the problem
result_distance, result_cost = dijkstra(n, edges, s, t)
# Output the result
print(result_distance, result_cost)sy389: 最短路径条数 简单
https://sunnywhy.com/sfbj/10/4/389
现有一个共个顶点（代表城市）、条边（代表道路）的无向图（假设顶点编号为从0到n-1），每条边有各自的边权，代表两个城市之间的距离。求从号城市出发到达号城市的最短距离和最短路径条数。
输入
第一行四个整数n、m、s、t（
接下来m行，每行三个整数u、v、w（
输出
输出两个整数，表示最短距离和最短路径条数，中间用空格隔开。
数据保证最短路径一定存在。
样例1
输入
4 5 0 2
0 1 2
0 2 5
0 3 1
1 2 1
3 2 2输出
3 2解释
对应的无向图如下图所示。
共有3条从0号顶点到2号顶点的路径：
0->3->2：距离为3；0->2：距离为5；0->1->2：距离为3。
因此最短距离为3，最短路径有2条。
以下是使用 Dijkstra 算法解决这个问题的 Python 代码：
import heapq
def dijkstra(n, edges, s, t):
graph = [[] for _ in range(n)]
for u, v, d in edges:
graph[u].append((v, d))
graph[v].append((u, d))
pq = [(0, s)] # (distance, node)
visited = set()
distances = [float('inf')] * n
distances[s] = 0
count = [0] * n
count[s] = 1
while pq:
dist, node = heapq.heappop(pq)
if node == t:
return dist, count[node]
if node in visited:
continue
visited.add(node)
for neighbor, d in graph[node]:
new_dist = dist + d
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
count[neighbor] = count[node]
elif new_dist == distances[neighbor]:
count[neighbor] += count[node]
# Read input
n, m, s, t = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]
# Solve the problem
result_distance, result_count = dijkstra(n, edges, s, t)
# Output the result
print(result_distance, result_count)这段代码首先构建了一个无向图的邻接表，并使用 Dijkstra 算法计算了从起始顶点到终点的最短距离和最短路径条数。然后将结果输出为两个整数，分别表示最短距离和最短路径条数。
sy390: 最短路径 中等
https://sunnywhy.com/sfbj/10/4/390
现有一个共n个顶点（代表城市）、m条边（代表道路）的无向图（假设顶点编号为从0到n-1），每条边有各自的边权，代表两个城市之间的距离。求从s号城市出发到达t号城市的最短距离和最短路径。
输入
第一行四个整数n、m、s、t（
接下来m行，每行三个整数u、v、w（
输出
min_d v_1->v_2->...->v_k按上面的格式输出最短距离和最短路径，其中min_d表示最短距离，v_1、v_2、...、v_k表示从起点到终点的最短路径上的顶点编号。
数据保证最短路径存在且唯一。
样例1
输入
4 5 0 2
0 1 2
0 2 5
0 3 1
1 2 2
3 2 2输出
3 0->3->2解释
对应的无向图如下图所示。
共有3条从0号顶点到2号顶点的路径：
0->3->2：距离为3；0->2：距离为5；0->1->2：距离为4。
因此最短距离为3，最短路径为0->3->2。
import heapq
def dijkstra(graph, start, end):
n = len(graph)
visited = [False] * n
distance = [float('inf')] * n
prev = [-1] * n
distance[start] = 0
pq = [(0, start)] # priority queue
while pq:
dist_u, u = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
for v, w in graph[u]:
if not visited[v] and dist_u + w < distance[v]:
distance[v] = dist_u + w
prev[v] = u
heapq.heappush(pq, (distance[v], v))
# Reconstruct path
path = []
while end != -1:
path.append(end)
end = prev[end]
path.reverse()
return distance, path
def main():
n, m, s, t = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
u, v, w = map(int, input().split())
graph[u].append((v, w))
graph[v].append((u, w))
distance, path = dijkstra(graph, s, t)
print(distance[t], '->'.join(map(str, path)))
if __name__ == "__main__":
main()sy391: 最短路径-多边权 中等
https://sunnywhy.com/sfbj/10/4/391
现有一个共n个顶点（代表城市）、m条边（代表道路）的无向图（假设顶点编号为从0到n-1），每条边有两种边权，分别代表两个城市之间的距离和花费。求从s号城市出发到达t号城市的最短距离，并在达到最短距离的路径中计算最少花费，同时给出相应的最短路径。
输入
第一行四个整数n、m、s、t（
接下来m行，每行四个整数u、v、w1、w2（
输出
min_d min_c v_1->v_2->...->v_k按上面的格式输出满足题意的最短距离（即mid_d）、达到最短路径的路径中的最少花费（即min_c）、相应的最短路径（v_1、v_2、...、v_k表示从起点到终点的最短路径上的顶点编号）。
数据保证这样的路径存在且唯一。
样例1
输入
4 5 0 2
0 1 2 1
0 2 5 1
0 3 1 2
1 2 1 6
3 2 2 3输出
3 5 0->3->2解释
对应的无向图如下图所示，其中边上的第一个数字为边权距离，第二个数字为边权花费。
共有3条从0号顶点到2号顶点的路径：
0->3->2：距离为3，花费为5；0->2：距离为5，花费为1；0->1->2：距离为3，花费为7。
因此最短距离为3，最短路径有2条，在这2条最短路径中的最少花费是5，对应的路径为0->3->2。
你可以稍微修改 Dijkstra 算法，使其能够同时考虑最短距离和最少花费的路径。下面是一个修改后的示例代码：
import heapq
def dijkstra(graph, n, start, end):
# 初始化距离、花费和路径
dist = [float('inf')] * n
cost = [float('inf')] * n
prev = [-1] * n # 用于重建路径
dist[start] = 0
cost[start] = 0
# 优先队列
queue = [(0, 0, start)] # (距离，花费，顶点)
while queue:
current_dist, current_cost, u = heapq.heappop(queue)
if u == end: # 若到达终点，则停止
break
# 遍历所有邻接点
for v, d, c in graph[u]:
temp_dist = current_dist + d
temp_cost = current_cost + c
# 如果找到更短的路径或花费更低的相同长度路径
if temp_dist < dist[v] or (temp_dist == dist[v] and temp_cost < cost[v]):
dist[v] = temp_dist
cost[v] = temp_cost
prev[v] = u
heapq.heappush(queue, (temp_dist, temp_cost, v))
# 重建路径
if dist[end] == float('inf'):
return "无法到达"
else:
path = []
at = end
while at != -1:
path.append(at)
at = prev[at]
path = path[::-1] # 反转路径
return dist[end], cost[end], '->'.join(map(str, path))
def solve(n, m, s, t, edges):
graph = [[] for _ in range(n)]
# 构建图
for u, v, w1, w2 in edges:
graph[u].append((v, w1, w2))
graph[v].append((u, w1, w2))
# 使用Dijkstra算法
min_distance, min_cost, shortest_path = dijkstra(graph, n, s, t)
return f"{min_distance} {min_cost} {shortest_path}"
# 输入
n, m, s, t = map(int, input().split())
edges = []
for _ in range(m):
u, v, w1, w2 = map(int, input().split())
edges.append((u, v, w1, w2))
# 解决问题
print(solve(n, m, s, t, edges))这段代码首先定义了一个修改后的 dijkstra 函数，该函数除了记录最短距离外，还记录了达到每个城市的最少花费。然后，在 main 函数中，它接受输入，构建图，并调用 dijkstra 函数来找到最短路径和相应的最少花费，最后输出结果。
sy392: 最短路径-多路径 中等
https://sunnywhy.com/sfbj/10/4/392
现有一个共n个顶点（代表城市）、m条边（代表道路）的无向图（假设顶点编号为从0到n-1），每条边有各自的边权，代表两个城市之间的距离。求从s号城市出发到达t号城市的最短路径条数和最短路径（可能有多条）。
输入
第一行四个整数n、m、s、t（
接下来m行，每行三个整数u、v、w（
输出
第一行输出一个整数，表示最短路径的条数；
接下来若干行，每行一条最短路径，格式如下：
v_1->v_2->...->v_k其中v_1、v_2、...、v_k表示从起点到终点的最短路径上的顶点编号。
注意，路径的输出顺序满足基于整数的字典序，即如果有两条路径a[1]->a[2]->...->a[k]->a[k+1]->...与b[1]->b[2]->...->b[k]->b[k+1]->...，满足a[1]==b[1]、a[2]==b[2]、...、a[k]==b[k]、a[k+1]<b[k+1]，那么把路径a优先输出。
样例1
输入
4 5 0 2
0 1 2
0 2 5
0 3 1
1 2 1
3 2 2输出
2
0->1->2
0->3->2解释
对应的无向图如下图所示。
共有3条从0号顶点到2号顶点的路径：
0->3->2：距离为3；0->2：距离为5；0->1->2：距离为3。
因此最短距离为3，最短路径为0->3->2和0->1->2。
要解决这个问题，我们可以使用一个稍微修改的Dijkstra算法来找出所有最短路径，同时记录每个节点的前驱节点列表以便于最后重建路径。这种方法可以确保我们找到所有的最短路径，并且能够在完成搜索后重构路径。此外，我们需要记录到达每个节点的最短路径数目。
以下是步骤的详细说明：
- 初始化：对于图中的每个节点，我们维护一个到达该节点的最短路径长度、到达该节点的最短路径数目，以及一个从该节点回溯到起点的前驱节点列表。
- Dijkstra算法：使用优先队列（最小堆）来选择当前未处理节点中距离起点最近的节点，进行松弛操作。不同于标准Dijkstra，当找到一条更短的路径到达某节点时，我们需要更新到达该节点的最短路径数目，并清空前驱节点列表，因为找到了一条更短的路径。如果找到的是一条等长的路径，我们则添加这条路径的最后一个节点到前驱节点列表中，并增加到达该节点的最短路径数目。
- 重建路径：从目标节点开始，使用前驱节点列表回溯至起点，这样可以找到所有的最短路径。这一步需要用到递归或队列的方法来实现。
- 输出路径：根据题目要求，我们需要按照特定的顺序输出所有找到的最短路径。可以通过递归回溯生成所有路径后，对路径进行排序，以满足输出要求。
下面是实现这一算法的Python代码：
from heapq import heappush, heappop
from collections import defaultdict
def dijkstra(graph, n, s, t):
dist = [float('inf')] * n
dist[s] = 0
prev = defaultdict(list)
queue = [(0, s)]
path_count = [0] * n
path_count[s] = 1
while queue:
d, u = heappop(queue)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heappush(queue, (dist[v], v))
prev[v] = [u]
path_count[v] = path_count[u]
elif dist[u] + w == dist[v]:
prev[v].append(u)
path_count[v] += path_count[u]
return dist, prev, path_count
def find_paths(prev, t):
def dfs(node):
if node == s:
return [[s]]
paths = []
for pred in prev[node]:
for path in dfs(pred):
paths.append(path + [node])
return paths
return dfs(t)
def solve(n, m, s, t, edges):
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w))
dist, prev, path_count = dijkstra(graph, n, s, t)
paths = find_paths(prev, t)
sorted_paths = sorted(paths, key=lambda x: [int(i) for i in x])
print(path_count[t])
for path in sorted_paths:
print("->".join(map(str, path)))
# 输入示例
n, m, s, t = map(int, input().split())
edges = []
for _ in range(m):
edges.append(tuple(map(int, input().split())))
solve(n, m, s, t, edges)这段代码定义了dijkstra函数来执行Dijkstra算法并计算最短路径的数量，find_paths函数来找到所有最短路径，最后的solve函数来处理输入数据和格式化输出结果。请注意，这个解决方案可能需要根据实际数据的不同进行调整以确保性能。
sy393: 最短距离-多起点多终点 中等
https://sunnywhy.com/sfbj/10/4/393
现有一个共n个顶点（代表城市）、m条边（代表道路）的无向图（假设顶点编号为从0到n-1），每条边有各自的边权，代表两个城市之间的距离。求从所有城市出发到达所有城市的所有最短距离。
输入
第一行两个整数n、m（
接下来m行，每行三个整数u、v、w（
输出
输出多行多列的整数，其中i号行j号列表示从号顶点到达号顶点的最短距离。如果无法到达，那么输出-1。整数之间用空格隔开，行末不允许有多余的空格。
样例1
输入
4 5
0 1 2
0 2 5
0 3 1
1 2 1
3 2 2输出
0 2 3 1
2 0 1 3
3 1 0 2
1 3 2 0解释
对应的无向图如下图所示。
这是一个典型的多源最短路径问题，可以使用 Floyd-Warshall 算法来解决。下面是一个实现：
def floyd_warshall(graph, n):
dist = [[float('inf')] * n for _ in range(n)]
# Initialize distances for direct edges
for u in range(n):
dist[u][u] = 0
for v, w in graph[u]:
dist[u][v] = w
# Update distances using Floyd-Warshall algorithm
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
def main():
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
u, v, w = map(int, input().split())
graph[u].append((v, w))
graph[v].append((u, w))
distances = floyd_warshall(graph, n)
for row in distances:
print(' '.join(str(d) if d != float('inf') else '-1' for d in row))
if __name__ == "__main__":
main()这段代码首先定义了一个 floyd_warshall 函数来执行 Floyd-Warshall 算法。然后，在 main 函数中，它接受输入，构建图，并调用 floyd_warshall 函数来找到所有城市之间的最短距离，并输出结果。
Floyd-Warshall 时间复杂度？不能用Dijkstra完成吗？
Floyd-Warshall 算法的时间复杂度为 O(n^3)，其中 n 是顶点的数量。这是因为 Floyd-Warshall 算法通过三重循环来更新所有顶点之间的最短距离。
虽然使用 Dijkstra 算法也可以解决多源最短路径问题，但是它需要对每个顶点运行一次单源最短路径算法，因此时间复杂度为 O(n * (n + m) * logn)，其中 m 是边的数量。在稠密图（边数量接近 n^2）的情况下，这可能比 Floyd-Warshall 算法更慢。
因此，在顶点数量较小且图比较稠密时，Floyd-Warshall 算法通常更加高效，因为它的时间复杂度不依赖于边的数量。而在稀疏图或者顶点数量很大时，Dijkstra 算法可能更适合，因为它的时间复杂度相对较低。
下面是一个使用 Dijkstra 算法解决多源最短路径问题的 Python 实现：
import heapq
def dijkstra(graph, start, n):
distances = [float('inf')] * n
for u in range(n):
if u == start:
distances[start] = 0
continue
visited = [False] * n
pq = [(0, start)] # priority queue，元素为 (distance, vertex)
while pq:
dist_u, u = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
for v, weight in graph[u]:
new_dist = dist_u + weight
if new_dist < distances[v]:
distances[v] = new_dist
heapq.heappush(pq, (new_dist, v))
return distances
def main():
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
u, v, w = map(int, input().split())
graph[u].append((v, w))
graph[v].append((u, w))
all_shortest_paths = []
for i in range(n):
shortest_paths_from_i = dijkstra(graph, i, n)
all_shortest_paths.append(shortest_paths_from_i)
for row in all_shortest_paths:
print(' '.join(str(d) if d != float('inf') else '-1' for d in row))
if __name__ == "__main__":
main()这个实现首先定义了一个 dijkstra 函数来执行 Dijkstra 算法，计算从给定起点到所有其他顶点的最短距离。然后，在 main 函数中，它接受输入，构建图，并调用 dijkstra 函数来找到所有城市之间的最短距离，并输出结果。
sy394: 最短路径-多边权II 中等
https://sunnywhy.com/sfbj/10/4/394
现有一个共n个顶点（代表城市）、m条边（代表道路）的无向图（假设顶点编号为从0到n-1），每条边有各自的边权，代表两个城市之间的距离；每个顶点有各自的点权，代表城市的堵车指数。求从s号城市出发到达t号城市的最短距离与最短路径。
输入
第一行四个整数n、m、s、t（
第二行为空格隔开的n个整数w1（0到n-1的城市的堵车指数；
接下来m行，每行三个整数u、v、w2（
输出
min_d v_1->v_2->...->v_k按上面的格式输出最短距离和最短路径，其中min_d表示最短距离，v_1、v_2、...、v_k表示从起点到终点的最短路径上的顶点编号。如果最短路径存在多条，那么输出路径上所有城市的堵车指数平均值最小的路径。数据保证这样的路径存在且唯一。
样例1
输入
4 5 0 2
2 3 2 1
0 1 2
0 2 5
0 3 1
1 2 1
3 2 2输出
3 0->3->2解释
对应的无向图如下图所示，其中边上的数字为边权距离，顶点旁的数字为点权堵车指数。
共有3条从0号顶点到2号顶点的路径：
0->3->2：距离为3，堵车指数平均值为； 0->2：距离为5，堵车指数平均值为； 0->1->2：距离为3，堵车指数平均值为。
因此最短距离为3，最小堵车指数平均值的最短路径为0->3->2。
这里是一个Dijkstra算法加DFS（深度优先搜索）来解决最短路径问题，并在路径长度相同的情况下优先选择平均堵车指数最小的路径。主要逻辑是先使用Dijkstra算法找出所有最短路径，然后通过DFS在这些路径中找到平均堵车指数最小的路径。
from collections import defaultdict
INF = float('inf')
class Edge:
def __init__(self, v, dis):
self.v = v
self.dis = dis
def dijkstra(n, s, G, weight):
d = [INF] * n
vis = [False] * n
pre = [[] for _ in range(n)]
d[s] = 0
for _ in range(n):
u, minDis = -1, INF
for j in range(n):
if not vis[j] and d[j] < minDis:
u, minDis = j, d[j]
if u == -1:
break
vis[u] = True
for edge in G[u]:
v, dis = edge.v, edge.dis
if not vis[v]:
if d[u] + dis < d[v]:
d[v] = d[u] + dis
pre[v] = [u]
elif d[u] + dis == d[v]:
pre[v].append(u)
return d, pre
def DFS(v, s, pre, weight, tempPath, optPath, optValue):
if v == s:
tempPath.append(v)
weightSum = sum(weight[node] for node in tempPath)
weightAvg = weightSum / len(tempPath)
if weightAvg < optValue[0]:
optValue[0] = weightAvg
optPath[:] = tempPath[:]
tempPath.pop()
return
tempPath.append(v)
for prev in pre[v]:
DFS(prev, s, pre, weight, tempPath, optPath, optValue)
tempPath.pop()
def solve(n, m, s, t, weight, edges):
G = defaultdict(list)
for u, v, w in edges:
G[u].append(Edge(v, w))
G[v].append(Edge(u, w))
d, pre = dijkstra(n, s, G, weight)
tempPath, optPath = [], []
optValue = [INF]
DFS(t, s, pre, weight, tempPath, optPath, optValue)
optPath.reverse()
return d[t], '->'.join(map(str, optPath))
# Example usage
n, m, s, t = map(int, input().split())
weight = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(m)]
min_d, path = solve(n, m, s, t, weight, edges)
print(f"{min_d} {path}")sy395: 交通枢纽 中等
https://sunnywhy.com/sfbj/10/4/395
现有一个共n个顶点（代表城市）、m条边（代表道路）的无向连通图（假设顶点编号为从0到n-1），每条边有各自的边权，代表两个城市之间的距离。为了促进城市间交流，需要从k个备选城市中选择其中一个城市作为交通枢纽，满足从这个交通枢纽出发到达其他所有城市的最短距离之和最小。
输入
第一行四个整数n、m、k（
接下来m行，每行三个整数u、v、w（
最后一行为空格隔开的k个整数，表示备选城市编号。
输出
输出两个整数，分别表示作为交通枢纽的城市编号、从交通枢纽出发到达其他所有城市的最短距离之和，中间用空格隔开。如果有多个满足条件的交通枢纽，那么输出城市编号最小的那个。
样例1
输入
4 5 2
0 1 1
0 2 5
0 3 3
1 2 2
2 3 4
0 2输出
0 7解释
对应的无向图如下图所示。
从0号城市到达1号、2号、3号城市的最短距离分别是1、3、3，因此最短距离之和是7；
从2号城市到达0号、1号、3号城市的最短距离分别是3、2、4，因此最短距离之和是9；
因此应选择0号城市作为交通枢纽，对应的最短距离之和为7。
您可以使用 Floyd-Warshall 算法来解决这个问题。该算法能够计算图中所有顶点对之间的最短路径。对于这个问题，我们只需要找到每个备选城市作为交通枢纽时，从该城市出发到其他所有城市的最短距离之和，然后选择最小的一个。
下面是一个实现：
def floyd_warshall(graph, n, candidates):
distances = [[float('inf')] * n for _ in range(n)]
for u in range(n):
distances[u][u] = 0
for u, v, w in graph:
distances[u][v] = w
distances[v][u] = w
for k in range(n):
for i in range(n):
for j in range(n):
distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])
min_total_distance = float('inf')
chosen_hub = -1
for hub in candidates:
total_distance = sum(distances[hub][v] for v in range(n) if v != hub)
if total_distance < min_total_distance:
min_total_distance = total_distance
chosen_hub = hub
return chosen_hub, min_total_distance
def main():
n, m, k = map(int, input().split())
graph = [tuple(map(int, input().split())) for _ in range(m)]
candidates = list(map(int, input().split()))
hub, min_total_distance = floyd_warshall(graph, n, candidates)
print(hub, min_total_distance)
if __name__ == "__main__":
main()您可以将您的输入和期望输出与上述代码一起运行以进行测试。