单源最短路径

定义

单源最短路径（Single Source Shortest Path）：对于一个带权图 $G = (V, E)$ ，其中每条边的权重是一个实数。另外，给定v中的一个顶点，称之为源点。则源点到其他所有各个顶点之间的最短路径长度，称之为单源最短路径。

路径长度指的是路径上各边权之和

常见解决单源最短路径问题的算法包括：

1、Dijkstra算法：一种贪心算法，用于解决无负权边的情况。它逐步扩展当前已知最短路径的范围，选择当前距离起始节点最近的节点，并更新该节点相邻的节点的距离

2、Bellman-Ford算法：适用于有负权边的情况。它通过多次迭代来逐步逼近最短路径，每次迭代都尝试通过更新边的权重来缩短路径。

3、SPFA 算法：优化的 Bellman-Ford 算法，它在每次迭代中不遍历所有的边，而是选择性地更新与当前节点相关的边，从而提高了算法的效率。

Dijkstra算法

在有权图（权值非负数）中求从起点到其他节点的最短路径算法

1、选源点到哪个节点近且该节点未被访问过

2、该最近节点被标记访问过

3、更新非访问节点到源点的距离，即更新minDist数组

朴素Dijkstra

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循环来寻找距离最近节点。这次直接遍历边，且通过堆来堆边进行排序，达到直接选择距离源点最近节点

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为节点数量），从而求得目标最短路

minDist[B] = min(minDist[A] + value, minDist[B])

Bellman-ford算法采用了动态规划的思想，即：将一个问题分解成多个决策阶段，通过状态之间的递归关系最后计算出全局最优解

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 算法每次都是对所有边进行松弛，其实是多做了一些无用功。

只需要对上一次松弛的时候更新过的节点作为出发节点所连接的边进行松弛就够了。

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())

参考

https://algo.itcharge.cn/08.Graph/04.Graph-Shortest-Path/01.Graph-Single-Source-Shortest-Path-01/#_1-%E5%8D%95%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E7%9A%84%E5%AE%9A%E4%B9%89

https://programmercarl.com/kamacoder/0094.%E5%9F%8E%E5%B8%82%E9%97%B4%E8%B4%A7%E7%89%A9%E8%BF%90%E8%BE%93I-SPFA.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC

单源最短路径 ​

定义 ​

Dijkstra算法 ​

朴素Dijkstra ​

堆优化版Dijkstra ​

Bellman-Ford算法 ​

SPFA 算法 ​

参考 ​