一、基本思路

1、Bellman-Ford算法概述

• Bellman - ford 算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在 n-1 次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。

• 负环判断： 假设 1 号点到 n 号点是可达的，每一个点同时向指向的方向出发，更新相邻的点的最短距离，通过循环 n-1 次操作，若图中不存在负环，则 1 号点一定会到达 n 号点，若图中存在负环，则在 n-1 次松弛后一定还会更新。

2、算法步骤

• for n次（如果限制只能走k条边，那这里循环次数到k）
• • 需要进行dis原始备份
• • for 所有边 a,b,w (松弛操作)
• • • dist[b] = min(dist[b],back[a] + w)

注意：back[] 数组是上一次迭代后 dist[] 数组的备份，由于是每个点同时向外出发，因此需要对 dist[] 数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点

3、注意事项

• 1. 循环完之后一定满足 dis[b] <= dis[a] + w 的三角不等式
• 2. 如果存在负权边，最短路不一定存在，原因在于可能形成负权回路，通过无数圈循环形成负无穷
• 3. 若限制经过边数 <= k 的时候，需要对 dis 备份操作 (详细原因见后面代码注释）

二、Java、C语言模板实现

//Java 模板实现
    static int N = 10010;
    static int n,k,m;
    static int x,y,z;
    static int INF = 0x3f3f3f3f;
    
    static PII[] edges = new PII[N];            // 对边权进行存储
    static int[] dis = new int[N];              // 点 1 到 n 的距离存储
    static int[] backup = new int[N];           // 进行dis的备份数组
    
    static String bellmanFord(){
        dis[1] = 0;                             // 初始化第一个节点的距离为 0
        
        for(int i = 1; i <= k; i++){            // 因为需要限制经过 k 条边
            
            backup = Arrays.copyOf(dis,N);      
            // 如果不使用原始的边权进行更新，那么在下面的边权循环更新过程中
            // 就会导致随着更新后面的点的距离也会发生变化，导致其他点距离也发生变化
            // 最后的结果就是导致限制的只能经过 k 条边的限制失效
            
            for(int j = 0; j < m; j++){
                PII temp = edges[j];            // 边权存储
                int aa = temp.a;
                int bb = temp.b;
                int cc = temp.c;
                dis[bb] = Math.min(dis[bb], backup[aa] + cc);       // 用原始的备份dis进行每个点距离的更新
            }
        }
        
        if(dis[n] >= INF/2){                    
            // 此处之所以是 INF/2 是因为存在负权边，不一定最后还是INF，可能已经更新了一条
            return "impossible";
        }
        
        return dis[n] + "";
    }

// 边权存储
class PII{
    int a;
    int b;
    int c;
    public PII(int a, int b, int c){
        this.a = a;
        this.b = b;
        this.c = c;
    }
}

```c
// C语言实现，此处是yxc实现
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

作者：yxc
链接：https://www.acwing.com/blog/content/405/

三、例题题解

// java题解实现
import java.util.*;

public class Main{
    static int N = 10010;
    static int n,k,m;
    static int x,y,z;
    static int INF = 0x3f3f3f3f;
    
    static PII[] edges = new PII[N];            // 对边权进行存储
    static int[] dis = new int[N];              // 点 1 到 n 的距离存储
    static int[] backup = new int[N];           // 进行dis的备份数组
    
    static String bellmanFord(){
        dis[1] = 0;                             // 初始化第一个节点的距离为 0
        
        for(int i = 1; i <= k; i++){            // 因为需要限制经过 k 条边
            
            backup = Arrays.copyOf(dis,N);      
            // 如果不使用原始的边权进行更新，那么在下面的边权循环更新过程中
            // 就会导致随着更新后面的点的距离也会发生变化，导致其他点距离也发生变化
            // 最后的结果就是导致限制的只能经过 k 条边的限制失效
            
            for(int j = 0; j < m; j++){
                PII temp = edges[j];            // 边权存储
                int aa = temp.a;
                int bb = temp.b;
                int cc = temp.c;
                dis[bb] = Math.min(dis[bb], backup[aa] + cc);       // 用原始的备份dis进行每个点距离的更新
            }
        }
        
        if(dis[n] >= INF/2){                    
            // 此处之所以是 INF/2 是因为存在负权边，不一定最后还是INF，可能已经更新了一条
            return "impossible";
        }
        
        return dis[n] + "";
    }
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        k = in.nextInt();
        
        for(int i = 0; i < N; i++){
            dis[i] = INF;
        }
        
        for(int i = 0; i < m; i++){
            x = in.nextInt();
            y = in.nextInt();
            z = in.nextInt();
            
            edges[i] = new PII(x, y, z);
        }
        
        String result = bellmanFord();
        

        System.out.println(result);

        
        
    }
}

class PII{
    int a;
    int b;
    int c;
    public PII(int a, int b, int c){
        this.a = a;
        this.b = b;
        this.c = c;
    }
}