bellman_ford算法与dijkstra为什么dijkstra算法不能计算带有负权边图

简介: bellman_ford算法与dijkstra为什么dijkstra算法不能计算带有负权边图

应用场景:带有负权边的图

为什么dijkstra算法不能计算带有负权边图

答:

dijkstra是一拳头买卖,一条边就经过一次,如果有负权边显然如果遍历多次这条边,最小值绝s对会更小。

所以bellman_ford算法大多的应用场景是在经过的边数有限制的情况下(能多次经过负权边但是有次数限制)

dijkstra算法(简介):

思路:

从源点开始(初始化为距离为0的那个点)也是自己确定的最小距离点

循环n(顶点数)次每一次确定一个距离最小值点,再用最小值点更新孩子节点,循环n次确定n个最小值点

通过点来更新其孩子(边只走一次)

bellman_ford算法

思路:

遍历n次,每次遍历所有的边,然后以父节点更新其出边(孩子节点)

遍历所有的边所以会遍历某个点的所有的入边,根据dist[i] + w[i] 和dist[x]该点的值]递推,即可得到最短距离

遍历n次所有的边,可以多次经过统一条边(可计算最大经过边数的最短路径(当有负权环的时候必须限定最大经理经历边数不然最小距离为负无穷))

代码:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
    static int N = 510;
    static int M = 100010;
    static int n;//总点数
    static int m;//总边数
    static int[] dist = new int[N];//从1到点到n号点的距离
    static Node[] list = new Node[M];//结构体
    static int INF = 500000000 + 5000000;
    public static void bellman_ford()
    {
        Arrays.fill(dist, INF);
        dist[1] = 0;
        //最长可能的最短路径不会超过n-1条边  循环n - 1次也就是最多经过n - 1条边
        for(int i = 0;i < n - 1;i++)
        {
            for(int j = 0;j < m;j++)
            {
                Node node = list[j];
                int a = node.a;
                int b = node.b;
                int c = node.c;
                dist[b] = Math.min(dist[b], dist[a] + c);
            }
        }
        if(dist[n] >= 500000000) System.out.println("-1");
        else System.out.println(dist[n]);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] str1 = reader.readLine().split(" ");
        n = Integer.parseInt(str1[0]);
        m = Integer.parseInt(str1[1]);
        for(int i = 0;i < m;i++)
        {
            String[] str2 = reader.readLine().split(" ");
            int a = Integer.parseInt(str2[0]);
            int b = Integer.parseInt(str2[1]);
            int c = Integer.parseInt(str2[2]);
            list[i] = new Node(a,b,c);
        }
        bellman_ford();
    }
}
class Node
{
    int a, b, c;
    public Node(int a,int b,int c)
    {
        this.a = a;
        this.b = b;
        this.c = c;
    }
}

增加功能检测负权回路(不存在最短路径)

for (int i = 0; i < n; i++) {
    int u = edges[i].source;
    int v = edges[i].destination;
    int w = edges[i].weight;            //经过n条边,如果可以更新毕然存在负权回路
    if (distance[u] != Integer.MAX_VALUE && distance[u] + w < distance[v]) {
        System.out.println("图中包含负权回路");
        return;
    }
}
目录
相关文章
|
1月前
|
机器学习/深度学习 算法
递归算法题练习(数的计算、带备忘录的递归、计算函数值)
递归算法题练习(数的计算、带备忘录的递归、计算函数值)
|
1月前
|
算法 Java
算法:Java计算二叉树从根节点到叶子结点的最大路径和
算法:Java计算二叉树从根节点到叶子结点的最大路径和
|
2月前
|
人工智能 算法 数据可视化
路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-2
路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-2
174 0
|
3月前
|
算法 搜索推荐 图计算
图计算中的社区发现算法是什么?请解释其作用和常用算法。
图计算中的社区发现算法是什么?请解释其作用和常用算法。
24 0
|
3月前
|
算法
最短路之Dijkstra算法
最短路之Dijkstra算法
24 0
|
2月前
|
存储 人工智能 算法
路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-1
路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-1
66 0
|
30天前
|
算法
关于Dijkstra算法
关于Dijkstra算法
|
3月前
|
算法 定位技术 Python
地图权重计算(算法题)
地图权重计算(算法题)
22 0
|
3月前
|
算法 搜索推荐 数据挖掘
图计算中的图算法有哪些常见的类型?请举例说明每种类型的算法。
图计算中的图算法有哪些常见的类型?请举例说明每种类型的算法。
31 0
|
3月前
|
算法 搜索推荐 Java
图计算中的PageRank算法是什么?请解释其作用和计算原理。
图计算中的PageRank算法是什么?请解释其作用和计算原理。
20 0