【笔记】数据结构与算法之最短路算法（Bellman_Ford）

QingYi.

适用于存在负权边的情况下

[Java] 纯文本查看 复制代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
    static class Edge{
        int a,b,w;
        Edge(int a,int b ,int w){
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }
    static int M = 100010;
    private static int N= 510,INF= 0x3f3f3f3f;
    static  Edge [] edges = new Edge[M];
    static int[] dist = new int[N];
    static int[] backup = new int[N];
    static int n,m,k;
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s = bf.readLine().split(" ");
//        总共n个点m条边且顶多经过k条边
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        k = Integer.parseInt(s[2]);
        for (int i = 0; i < m; i++) {
            String []  re = bf.readLine().split(" ");
            //分别是第一条边和第二条边
            int a = Integer.parseInt(re[0]);
            int b = Integer.parseInt(re[1]);
            //距离
            int w = Integer.parseInt(re[2]);
            edges[i] = new Edge(a,b,w);
        }
        int res = bellmanFord();
        //找不到最短路，例如有负权边进入死循环导致正无穷大
        if (res==-1){
            System.out.println("impossible");
        }else {
            System.out.println(res);
        }
    }




    private static int bellmanFord() {
        //初始化操作
        Arrays.fill(dist,INF);
        dist[1] = 0;
        //循环顶多进行k次
        for (int i = 0; i < k; i++) {
            backup = dist.clone();
            for (int j = 0; j < m; j++) {
                int a = edges[j].a;
                int b = edges[j].b;
                int w = edges[j].w;
                //使用备份去避免串联，用无穷大来更新，取得最小值
                dist[b] = Math.min(dist[b],backup[a]+w);
            }
        }
        //因为有最大值INF,还有负权，加上负权边可能不是INF了，可能比INF小，所以判断大于一半就行
        if (dist[n]>INF/2){
            return -1;
        }
        return dist[n];
    }
}

在新标签打开所有链接复制所有链接URL复制所有链接URL（反向）复制所有链接标题 + URL复制所有链接标题 + URL (MD)复制所有链接标题 + URL (BBS)复制所有链接标题 + URL (筛选)复制所有链接标题 + URL (设置复制格式)在新标签页打开所有图片链接在一个标签页显示所有图片链接
复选框 - 选中
复选框 - 取消
复选框 - 反选
单选框 - 选中
单选框 - 取消
特殊单选框 - 选中