$$\color{Red}{Bellman_ford-三种语言实现全解析}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思路

Bellman_ford最短路问题

1.时间复杂度方面

总的时间复杂度为O(nm)

2.算法原理

Bellman_ford算法的解决对象是出现负权边且要求有限指定边数下的最短路，具体操作是在k次for循环中，将m条边
进行依次进行类似三角形两边之和与第三边取最短的松弛操作

dist[b] = min(dist[b], backup[a] + w);

3.算法细节

• 为什么不能使用Djkstra算法来解决负权边问题？

Dijkstra算法每次更新，锁定了最短边的长度，但是后续边中若出现了负回路，那么可能之前锁定的边回到起点的最短距离就不再是之前更新的那个距离了，但是它已经被锁定无法更新，这样就导致着一步错步步错

• 为什么使用结构体数组来存储图的点和边权？而不是之前的邻接矩阵或邻接表？

Dijkstra的意义是找寻到它的邻点并更新，邻接矩阵虽然体现的没那么深刻（刷新似乎是全点），但是实际上非邻点会因为判断语句的最小值判断保持值不变。堆优化深刻体现了这一意义，而Bellman_ford是全边刷新

• 为什么使用了一个back[N]对标dist[N]进行复制操作？

我们刷新的过程中，前面的点得到了更新，但是后面的点不能用前面刚更新的点去继续更新，这么就会导致
短路错误。因此我们k次更新的每次更新前都会memcpy当前dist数组到back，用整个back数组去松弛dist

• 为什么判断为不可达的条件和之前的相等不同，而是If ( dist[n] > 0x3f3f3f3f / 2 )?

我们看似定义了一个无穷，但是出现负权边还是会缩小这个看似无穷的值，所以还用相等判别就不现实了

1. java

import java.util.*;

class edge {
    int a, b, w;
    public edge(int a, int b, int w){
        this.a = a;
        this.b = b;
        this.w = w;
    }
}

public class Main {
    static int N = 510, M = 10010, n, m, k, max = 0x3f3f3f3f;
    static int d[] = new int [N];
    static edge edges[] = new edge [M];

    public static void bellman_ford() {
        Arrays.fill(d, max);
        d[1] = 0;

        for (int i=0; i<k; i++) {
            //因为是-》n所以共n+1个位数
            int [] back = Arrays.copyOf(d, n+1);

            for(int j=0; j<m; j++){
                edge x = edges[j];
                int a = x.a;
                int b = x.b;
                int w = x.w;
                d[b] = Math.min(d[b], back[a] + w);
            }
        }
        if (d[n] > max / 2) System.out.println("impossible");
        else System.out.println(d[n]);
    }

    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();

        for(int i=0; i<m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int w = sc.nextInt();
            edges[i] = new edge(a, b, w);
        }

        bellman_ford();
    }
}

2.python3 代码

N = int(1e4 + 10)
d = [0x3f3f3f3f] * N
Edge = []

def bellman_ford():
    d[1] = 0
    for i in range(k):
        # 限制条件K条边到n,故循环K次
        back = d.copy()
        # m条边故循环m次更新
        for j in range(m):
            a, b, w = Edge[j]
            d[b] = min(d[b], back[a] + w)

    if d[n] >= 0x3f3f3f3f // 2: return 'impossible'
    else:   return d[n]

if __name__ == '__main__':
    n, m, k = map(int, input().split())
    for i in range(m):
        x, y, z = map(int, input().split())
        Edge.append([x, y, z])

    print(bellman_ford())

3.C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 1e4 + 10;
//存储最短路径
int dist[N]; 
//在松弛操作前，备份之前最短路径，防止出现本不该更新最短路径的串联现象
int back[N];

struct Edge{
    int a, b, w;
}e[M];

int n, m, k;

bool bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    //最远k条边，即刷新k次，若距离还为无穷，则说明无法走到
    for(int i=0; i<k; i++)
    {
        //每次都需要刷新当前备份数组
        memcpy(back, dist, sizeof dist);
        //一共m条边，故遍历全部边
        for(int j=0; j<m; j++)
        {
            int a = e[j].a, b = e[j].b, w = e[j].w;
            //三角形松弛刷新
            dist[b] = min(dist[b], back[a] + w);
        }
    }

    //这里和dijkstra不同，不是==0x3f3f3f3f是因为使用松弛操作
    //会把我们本想仍为正无穷的点，刷新为小于预设无穷的情况
    if(dist[n] > 0x3f3f3f3f / 2)    return false;
    return true;

}

int main()
{
    int x, y, z;
    scanf("%d%d%d", &n, &m, &k);

    //结构体数组赋值
    for(int i=0; i<m; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        e[i] = {x, y, z};
    }


    if(!bellman_ford()) puts("impossible");
    else cout << dist[n] << endl;

    return 0;
}