带负权值的图如何计算最短路径？

• 博主简介: 努力学习的23级 软件工程专业 本科生一枚 🌸
• 博主主页 ： @灰阳阳
• 每日一言 🌟：“你若盛开，清风自来。” —— 三毛

前言

处理父权值Dijkstra和Floyd两个算法实际上都可以用，但是要注意处理负权环 🚨。所谓负权环就是：从当前结点经过一定路径回到原来结点，由于有某些边有负权值，导致绕玩一圈，的权值比0还小，绕无限圈，权值就会无限小，这种环是无意义的，成为负权环。Dijkstra 是基于贪心策略的，遇到负权环可能贪心策略会出错。Floyd 遇到负权环，会死循环 😱。

因此处理带有负权值的图，我们建议用下面这种算法去实现——Bellman-Ford算法 💡

Bellman-Ford算法

算法简介

Bellman-Ford算法是一种求单元最短路径的算法，可以处理有向图或者无向图带正\负权值的最短路径问题。但时间复杂度高：$O(V\times E)$ (V、E分别是边、点个数)。

算法步骤

1. 根据题意，读入所边的信息（起点、终点、权值），存到集合中，比如用邻接表。
2. 初始化一个距离数组$dist[i]$ ，表示从指定起点（起点根据题目而定）到结点$i$的最短路径
3. 假设图一共有$n$个结点，最所有边进行松弛操作，重复$n-1$次，进而更新$dist$数组。
4. 最终$dist[i]$ 就是从指定起点到达$i$结点的最短路径。

什么是松弛？
松弛简单来说就是更换从起点到达i号结点的最短路线（权值）💥。例如：

从from到to结点，原本的路线是3+7=10，但现在有一条路线更短：5+1=6,我们把3+7=10更换成5+1=6就是对结点to的松弛操作。

基础实践1

1、题目信息

最短路

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

如下图所示，G 是一个无向图，其中蓝色边的长度是 1、橘色边的长度是2、绿色边的长度是 3 。

则从A到 S 的最短距离是多少？（直接输出答案即可）
考虑到可能有和我一样无法准确识别某些颜色的小可爱，这里已经把图建立好了：

import java.util.*;

public class Main {
    private static final Scanner in = new Scanner(System.in);
    private static List<int[]> edges = new ArrayList<>();

    public static void main(String[] args) {
        add('A', 'C', 1);
        add('A', 'D', 1);
        add('A', 'E', 1);
        add('D', 'E', 1);
        add('E', 'I', 1);
        add('D', 'H', 1);
        add('H', 'I', 1);
        add('B', 'G', 1);
        add('F', 'G', 1);
        add('F', 'J', 1);
        add('K', 'N', 1);
        add('L', 'M', 1);
        add('N', 'P', 1);
        add('P', 'O', 1);
        add('O', 'Q', 1);
        add('Q', 'M', 1);
        add('L', 'R', 1);
        add('S', 'R', 1);
        add('M', 'S', 1);

        add('A', 'B', 2);
        add('B', 'J', 2);
        add('D', 'I', 2);
        add('D', 'G', 2);
        add('G', 'K', 2);
        add('K', 'P', 2);
        add('J', 'S', 2);
        add('M', 'N', 2);
        add('H', 'L', 2);

        add('E', 'I', 3);
        add('I', 'M', 3);
        add('G', 'I', 3);
        add('C', 'D', 3);
        add('C', 'G', 3);
        add('C', 'F', 3);
        add('O', 'R', 3);
        add('K', 'L', 3);
        
    }

    private static void add(char u, char v, int w) {
        edges.add(new int[] {u, v, w});
        edges.add(new int[] {v, u, w});
    }
}

2、AC代码

这道题目比较简单，Djkstra和Floyd两个算法做的很容易，因此我们就选择Bellman-Ford算法吧 😎。

import java.util.*;

public class Main {
    private static final Scanner in = new Scanner(System.in);
    private static List<int[]> edges = new ArrayList<>();

    public static void main(String[] args) {
        add('A', 'C', 1);
        add('A', 'D', 1);
        add('A', 'E', 1);
        add('D', 'E', 1);
        add('E', 'I', 1);
        add('D', 'H', 1);
        add('H', 'I', 1);
        add('B', 'G', 1);
        add('F', 'G', 1);
        add('F', 'J', 1);
        add('K', 'N', 1);
        add('L', 'M', 1);
        add('N', 'P', 1);
        add('P', 'O', 1);
        add('O', 'Q', 1);
        add('Q', 'M', 1);
        add('L', 'R', 1);
        add('S', 'R', 1);
        add('M', 'S', 1);

        add('A', 'B', 2);
        add('B', 'J', 2);
        add('D', 'I', 2);
        add('D', 'G', 2);
        add('G', 'K', 2);
        add('K', 'P', 2);
        add('J', 'S', 2);
        add('M', 'N', 2);
        add('H', 'L', 2);

        add('E', 'I', 3);
        add('I', 'M', 3);
        add('G', 'I', 3);
        add('C', 'D', 3);
        add('C', 'G', 3);
        add('C', 'F', 3);
        add('O', 'R', 3);
        add('K', 'L', 3);

        /**
         * 因为每个结点都是大写字母，Z的ascii码是90，所以长度选择大于90的就可以*/
        //定义距离数组
        int[] dist=new int[150];
        //初始化成极大值
        Arrays.fill(dist, Integer.MAX_VALUE/2);
        //用来备份dist的数组
        int[] tep=new int[150];

        //设定起始节点(从A结点开始)
        dist['A']=0;

        //进行n-1次松弛（n是结点个数）
        for(int i=0;i<edges.size()-1;i++){
            tep=Arrays.copyOf(dist,dist.length);
            for(int[] edge:edges){
                int from=edge[0];
                int to=edge[1];
                int weight=edge[2];
                if(tep[from]!=Integer.MAX_VALUE/2&&dist[to]>tep[from]+weight){
                    dist[to]=tep[from]+weight;
                }
            }
        }
        
        //A到S的最短距离
        System.out.println(dist['S']);
    }

    private static void add(char u, char v, int w) {
        edges.add(new int[] {u, v, w});
        edges.add(new int[] {v, u, w});
    }
}

基础实践2

1、题目信息

853. 有边数限制的最短路

问题描述

给定一个 ( n ) 个点 ( m ) 条边的有向图，图中可能存在重边和自环，边权可能为负数。请你求出从 1 号点到 ( n ) 号点的最多经过 ( k ) 条边的最短距离，如果无法从 1 号点走到 ( n ) 号点，输出 impossible。注意：图中可能 存在负权回路⚠️。

输入格式

第一行包含三个整数 $n,m,k$。

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

点的编号为 $1\sim n$。

输出格式

输出一个整数，表示从 1 号点到 $n$ 号点的最多经过 $k$ 条边的最短距离。

如果不存在满足条件的路径，则输出 impossible。

数据范围

$[1\le n,k\le 500,]$

$[1\le m\le 10000,]$

$[1\le x,y\le n,]$

任意边长的绝对值不超过 $10000$。

输入样例：

3 3 1
1 2 1
2 3 1
1 3 3

输出样例：

3

2、AC代码

import java.util.*;
public class Main {

    static class Node{
        int from,to,weight;
        public Node(int from, int to, int weight){
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    //边的个数题目最多是10000，这里冗余9（编号从1开始）
    static Node[] edges=new Node[10010];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k=sc.nextInt();

        //把边的信息存到邻接表中
        for(int i=0;i<m;i++){
            int from=sc.nextInt();
            int to=sc.nextInt();
            int weight=sc.nextInt();
            edges[i]=new Node(from,to,weight);
        }

        //定义距离数组，存最短路路径
        int[] dist=new int[n+1];
        Arrays.fill(dist,Integer.MAX_VALUE/2);
        dist[1]=0;//设定起点（编号从1开始）

        //备份最短路径
        int[] temp=new int[n+1];

        for(int i=0;i<k;i++){
            temp=Arrays.copyOf(dist,dist.length);
            for(int j=0;j<m;j++){
                int from=edges[j].from;
                int to=edges[j].to;
                int weight=edges[j].weight;

                //可达，并且找到更短距离，松弛
                if(temp[from]!=Integer.MAX_VALUE/2&&dist[to]>temp[from]+weight){
                    dist[to]=temp[from]+weight;
                }
            }
        }

        //不可达，输出不可能
        if(dist[n]==Integer.MAX_VALUE/2){
            System.out.println("impossible");
        }else{//反之亦然
            System.out.println(dist[n]);
        }
    }
}

最后的补充

在基础实践2中的代码中虽然可以求出最短路径，但Bellman-Ford算法的功能不止于此，他还可以检测图中是否存在负权环 😈，搜索出环的位置。 （把Floyd和Dijkstra羡慕坏了ψ(｀∇´)ψ）

1、检测是否存在负权环

如果进行第$V$次松弛，还能找到最短路径，那么就存在负权环（V是结点个数）⚠️。

import java.util.*;

public class Main {

    static class Edge {
        int from, to, weight;
        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 顶点数
        int m = sc.nextInt(); // 边数

        Edge[] edges = new Edge[m];
        for (int i = 0; i < m; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            int weight = sc.nextInt();
            edges[i] = new Edge(from, to, weight);
        }

        int[] dist = new int[n + 1]; // 距离数组
        Arrays.fill(dist, Integer.MAX_VALUE / 2);
        dist[1] = 0; // 假设起点是 1

        int lastUpdatedNode = -1; // 记录最后一次更新的节点

        // Bellman-Ford 算法
        for (int i = 0; i < n; i++) {
            lastUpdatedNode = -1;
            for (Edge edge : edges) {
                if (dist[edge.from] != Integer.MAX_VALUE / 2 && dist[edge.to] > dist[edge.from] + edge.weight) {
                    dist[edge.to] = dist[edge.from] + edge.weight;
                    lastUpdatedNode = edge.to; // 记录最后一次更新的节点（如果存在更短路径）
                }
            }
        }

        // 检测负权环
        if (lastUpdatedNode != -1) {
            System.out.println("图中存在负权环！");
        } else {
            System.out.println("图中不存在负权环。");
        }
    }
}

2、负权环的位置

如何按顺序打印这个负权环呢？
首先，我们可以找环的入口，这个很简单，在第V次松弛的时候，还能更新to结点的最短路，to就是负权环的入口了；
最后，一个就是串联起来了，我们可以使用回溯的方式来进行，即定义parent数组，parent[i]表示i结点的父结点，当找到start（入口结点），借助parent数组就可以回溯找到整个环。 🔄

import java.util.*;

public class Main {

    static class Edge {
        int from, to, weight;

        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 顶点数
        int m = sc.nextInt(); // 边数

        Edge[] edges = new Edge[m];
        for (int i = 0; i < m; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            int weight = sc.nextInt();
            edges[i] = new Edge(from, to, weight);
        }

        int[] dist = new int[n + 1]; // 距离数组
        int[] parent = new int[n + 1];//parent[i]表示结点i的父节点，用于回溯寻找负权环
        Arrays.fill(dist, Integer.MAX_VALUE / 2);
        dist[1] = 0; // 假设起点是 1

        int lastUpdatedNode = -1; // 记录最后一次更新的节点

        // Bellman-Ford 算法（第n次松弛用于检查是否存在负权环）
        for (int i = 0; i < n; i++) {
            lastUpdatedNode = -1;
            for (Edge edge : edges) {
                if (dist[edge.from] != Integer.MAX_VALUE / 2 && dist[edge.to] > dist[edge.from] + edge.weight) {
                    dist[edge.to] = dist[edge.from] + edge.weight;
                    parent[edge.to] = edge.from;
                    lastUpdatedNode = edge.to; // 记录最后一次更新的节点（如果存在更短路径）
                }
            }
        }

        // 检测负权环
        if (lastUpdatedNode != -1) {
            System.out.println("图中存在负权环！");

            //存在负权环，lastUpdatedNode就是环的入口结点！
            int start = lastUpdatedNode;
            List<Integer> list = new ArrayList<>();//存环的结点集合
            for (int v = start; ; v = parent[v]) {
                //枚举一圈退出循环
                if (v == start && list.size() > 1) break;
                list.add(v);//记录环中结点，按顺序
            }
            
            //打印环
            for (int a : list) {
                System.out.print(a + "->");
            }
        } else {
            System.out.println("图中不存在负权环。");
        }
    }
}