851 spfa求最短路（spfa求解最短路径）

落日映苍穹つ 2022-09-15 15:43 129阅读 0赞

**1. 问题描述：**

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。数据保证不存在负权回路。

**输入格式**

第一行包含整数 n 和 m。接下来 m 行每行包含三个整数 x，y，z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

**输出格式**

输出一个整数，表示 1 号点到 n 号点的最短距离。如果路径不存在，则输出 impossible。

**数据范围**

1 ≤ n，m ≤ 10 ^ 5，  
图中涉及边长绝对值均不超过 10000。

**输入样例：**

3 3  
1 2 5  
2 3 -3  
1 3 4

**输出样例：**

2  
来源：[https://www.acwing.com/problem/content/description/853/][https_www.acwing.com_problem_content_description_853]

**2. 思路分析：**

这道题目属于**spfa**的模板题，spfa算法主要用来求解图中存在负权边的单源最短路径问题（从起点到终点的最短路径），主要借助于一个队列来实现，算法的核心是如果通过中间点j到达某一个点k的距离更短那么更新从起点到这个点的最短距离并且将这个修改的点加入到队列中直到队列中没有被修改的点为止，可以使用库函数中的队列也可以使用数组来模拟队列（可以写一个循环队列），因为使用的是python语言，所以可以使用python中的deque函数表示双端队列；

**3. 代码如下：**

**每一个g\[i\]都是一个字典：**

from typing import List
    import collections
    
    
    class Solution:
        # s为起点, t为终点, n为图中节点的个数, g为有向图
        def spfa(self, s: int, t: int, n: int, g: List[dict]):
            # 双端队列
            q = collections.deque()
            # 队列中只存节点的编号即可, 因为起点到某个点的最短距离存储在了dis中
            q.append(s)
            # 标记某个点是否被修改, 好像声明为布尔值比整型列表会快一点
            vis = [False] * (n + 1)
            vis[s] = True
            INF = 10 ** 9
            # 存储起点到所有点的最短距离
            dis = [INF] * (n + 1)
            # 自己到自己的距离为0
            dis[s] = 0
            while q:
                p = q.popleft()
                # 出队之后将标记修改为未修改, 因为在后面的时候这个点还可能被修改
                vis[p] = False
                for next in g[p].items():
                    # 通过当前的节点p到下一个点的距离更短说明需要将修改的点加入到队列中
                    if dis[next[0]] > dis[p] + next[1]:
                        dis[next[0]] = dis[p] + next[1]
                        # 判断发生修改的节点是否在队列中, 不在队列中则需要将其加入到队列中
                        if vis[next[0]] == 0:
                            q.append(next[0])
                            vis[next[0]] = True
            return dis[t] if dis[t] != INF else "impossible"
    
        def process(self):
            n, m = map(int, input().split())
            # 每一个g[i]都是一个字典
            g = [dict() for i in range(n + 1)]
            for i in range(m):
                x, y, z = map(int, input().split())
                # 当有重边的时候取最短的那条边
                if y in g[x]:
                    g[x][y] = min(g[x][y], z)
                else:
                    g[x][y] = z
            return self.spfa(1, n, n, g)
    
    
    if __name__ == "__main__":
        print(Solution().process())

**每一个g\[i\]都是一个list列表：**

from typing import List
    import collections
    
    
    class Solution:
        def spfa(self, s: int, t: int, n: int, g: collections.defaultdict):
            # 注意队列只存顶点即可, 不用存距离, 这样会快很多
            q = collections.deque()
            q.append(s)
            vis = [False] * (n + 1)
            vis[s] = True
            INF = 10 ** 9
            dis = [INF] * (n + 1)
            dis[s] = 0
            while q:
                # 注意是popleft而不是pop
                p = q.popleft()
                vis[p] = False
                for next in g[p]:
                    if dis[next[0]] > dis[p] + next[1]:
                        dis[next[0]] = dis[p] + next[1]
                        if vis[next[0]] == 0:
                            q.append(next[0])
                            vis[next[0]] = True
            return dis[t] if dis[t] != INF else "impossible"
    
        def process(self):
            n, m = map(int, input().split())
            # 每一个g[i]都是一个字典
            g = collections.defaultdict(list)
            for i in range(m):
                x, y, z = map(int, input().split())
                g[x].append((y, z))
            return self.spfa(1, n, n, g)
    
    
    if __name__ == "__main__":
        print(Solution().process())

**不写成方法的形式这样会比较快一点（调用方法的时候还需要一定的时间）：**

import collections
    if __name__ == "__main__":
        n, m = map(int, input().split())
        # 每一个g[i]都是一个字典
        g = [dict() for i in range(n + 1)]
        for i in range(m):
            x, y, z = map(int, input().split())
            if y in g[x]:
                g[x][y] = min(g[x][y], z)
            else:
                g[x][y] = z
        # 注意队列只存顶点即可, 不用存距离, 这样会快很多
        q = collections.deque()
        s, t = 1, n
        q.append(s)
        vis = [False] * (n + 1)
        vis[s] = True
        INF = 10 ** 9
        dis = [INF] * (n + 1)
        dis[s] = 0
        while q:
            # 注意是popleft而不是pop
            p = q.popleft()
            vis[p] = False
            for next in g[p].items():
                if dis[next[0]] > dis[p] + next[1]:
                    dis[next[0]] = dis[p] + next[1]
                    if vis[next[0]] == 0:
                        q.append(next[0])
                        vis[next[0]] = True
        print(dis[t] if dis[t] != INF else "impossible")

[https_www.acwing.com_problem_content_description_853]: https://www.acwing.com/problem/content/description/853/