单源最短路径
定义
单源最短路径（Single Source Shortest Path）：对于一个带权图
路径长度指的是路径上各边权之和
常见解决单源最短路径问题的算法包括：
1、Dijkstra算法：一种贪心算法，用于解决无负权边的情况。它逐步扩展当前已知最短路径的范围，选择当前距离起始节点最近的节点，并更新该节点相邻的节点的距离
2、Bellman-Ford算法：适用于有负权边的情况。它通过多次迭代来逐步逼近最短路径，每次迭代都尝试通过更新边的权重来缩短路径。
3、SPFA 算法：优化的 Bellman-Ford 算法，它在每次迭代中不遍历所有的边，而是选择性地更新与当前节点相关的边，从而提高了算法的效率。
Dijkstra算法
在有权图（权值非负数）中求从起点到其他节点的最短路径算法
1、选源点到哪个节点近且该节点未被访问过
2、该最近节点被标记访问过
3、更新非访问节点到源点的距离，即更新minDist数组
朴素Dijkstra
py
import sys
def dijkstra(n, m, edges, start, end):
# 初始化邻接矩阵
grid = [[float('inf')] * (n + 1) for _ in range(n + 1)]
for p1, p2, val in edges:
grid[p1][p2] = val
# 初始化距离数组和访问数组
minDist = [float('inf')] * (n + 1)
visited = [False] * (n + 1)
minDist[start] = 0 # 起始点到自身的距离为0
for _ in range(1, n + 1): # 遍历所有节点
minVal = float('inf')
cur = -1
# 选择距离源点最近且未访问过的节点
for v in range(1, n + 1):
if not visited[v] and minDist[v] < minVal:
minVal = minDist[v]
cur = v
if cur == -1: # 如果找不到未访问过的节点，提前结束
break
visited[cur] = True # 标记该节点已被访问
# 更新未访问节点到源点的距离
for v in range(1, n + 1):
if not visited[v] and grid[cur][v] != float('inf') and minDist[cur] + grid[cur][v] < minDist[v]:
minDist[v] = minDist[cur] + grid[cur][v]
return -1 if minDist[end] == float('inf') else minDist[end]
if __name__ == "__main__":
input = sys.stdin.read
data = input().split()
n, m = int(data[0]), int(data[1])
edges = []
index = 2
for _ in range(m):
p1 = int(data[index])
p2 = int(data[index + 1])
val = int(data[index + 2])
edges.append((p1, p2, val))
index += 3
start = 1 # 起点
end = n # 终点
result = dijkstra(n, m, edges, start, end)
print(result)堆优化版Dijkstra
朴素版本是通过遍历节点来遍历边，通过两层for循环来寻找距离最近节点。这次直接遍历边，且通过堆来堆边进行排序，达到直接选择距离源点最近节点
py
import heapq
class Edge:
def __init__(self, to, val):
self.to = to
self.val = val
def dijkstra(n, m, edges, start, end):
grid = [[] for _ in range(n + 1)]
for p1, p2, val in edges:
grid[p1].append(Edge(p2, val))
minDist = [float('inf')] * (n + 1)
visited = [False] * (n + 1)
pq = []
heapq.heappush(pq, (0, start))
minDist[start] = 0
while pq:
cur_dist, cur_node = heapq.heappop(pq)
if visited[cur_node]:
continue
visited[cur_node] = True
for edge in grid[cur_node]:
if not visited[edge.to] and cur_dist + edge.val < minDist[edge.to]:
minDist[edge.to] = cur_dist + edge.val
heapq.heappush(pq, (minDist[edge.to], edge.to))
return -1 if minDist[end] == float('inf') else minDist[end]
# 输入
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
start = 1 # 起点
end = n # 终点
# 运行算法并输出结果
result = dijkstra(n, m, edges, start, end)
print(result)Bellman-Ford算法
带负权值的单源最短路问题
核心思想是对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路
py
minDist[B] = min(minDist[A] + value, minDist[B])Bellman-ford算法采用了动态规划的思想，即：将一个问题分解成多个决策阶段，通过状态之间的递归关系最后计算出全局最优解
py
def main():
n, m = map(int, input().strip().split())
edges = []
for _ in range(m):
src, dest, weight = map(int, input().strip().split())
edges.append([src, dest, weight])
minDist = [float("inf")] * (n + 1)
minDist[1] = 0 # 起点处距离为0
for i in range(1, n):
updated = False
for src, dest, weight in edges:
if minDist[src] != float("inf") and minDist[src] + weight < minDist[dest]:
minDist[dest] = minDist[src] + weight
updated = True
if not updated: # 若边不再更新，即停止回圈
break
if minDist[-1] == float("inf"): # 返还终点权重
return "unconnected"
return minDist[-1]
if __name__ == "__main__":
print(main())SPFA 算法
Bellman-ford算法每次松弛都是对所有边进行松弛
但真正有效的松弛，是基于已经计算过的节点在做的松弛
所以 Bellman_ford 算法 每次都是对所有边进行松弛，其实是多做了一些无用功。
只需要对 上一次松弛的时候更新过的节点作为出发节点所连接的边 进行松弛就够了。
py
import collections
def main():
n,m=map(int,input().strip().split())
edges=[[] for _ in range(n+1)]
for _ in range(m):
src,dest,wright=map(int,input().strip().split())
edges[src].append([dest,weight])
minDist=[float("inf")]*(n+1)
minDist[1]=0
que=collections.deque([1])
visited=[False]*(n+1)
visited[1]=True
while que:
cur=que.popleft()
visited[cur]=False
for dest,weight in edges[cur]:
if minDist[cur]!=float('inf') and minDist[cur]+weight<minDist[dest]:
minDist[dest]=minDist[cur]+weight
if visited[dest]==False:
que.append(dest)
visited[dest]=True
if minDist[-1]==float("inf"):
return "unconnected"
return minDist[-1]
if __name__=="__main__":
print(main())