最短路Dijkstra算法讲解

最短路Dijkstra算法讲解

还是以举例子为主吧,部分图片来自于网络。

在下边的学习中,主要是通过松弛操作让最短路的值进行替换。dijie斯特拉指定一个点(源点)到其余的各个顶点的最短路径,也叫做“单源最短路径”。

例如下图中的1号顶点到2,3,4,5,6顶点的最短路径:

最短路Dijkstra算法讲解

 

在这里要和flody算法一样,在这儿也需要用二维数组e来存取顶点之间和边之间的关系,数值如下:

最短路Dijkstra算法讲解

在这儿我们还需要用一个一维数组dis来存取1号顶点到各个顶点的初始路程,如下:

最短路Dijkstra算法讲解

因为dis中存取的是各个顶点到1号顶点的初始距离,所以我们把dis数组中的值称为最短路的“估计值”。

既然我们是求1号顶点到其余各个顶点的最短路程,那我们就可以先找一个距离1号顶点比较近的顶点。

我们通过看dis数组可知距离1号最近的是2号顶点。当我们选择了2号顶点之后,dis[2] 中的值由一个“估计值”变成了一个“确定值”,即1号顶点到2号顶点的最短路程就变成了当前的dis[2]的值。

当我们选定了2号顶点,我们接下来看2号顶点有哪些出边,有2–>3和2–>4这两条边,我们可以通过讨论2–>3这条边是否让1号到3号顶点的路程,也就是说现在我们来比较dis[3] 和 dis[2] + e[2][3] 的大小,其中dis[3] 表示1号顶点到3号顶点的路程:dis[2]
+e[2][3]中dis[2]表示1号顶点到2号顶点的路程, e[2][3]表示2–>3这条边。所以dis[2] + dis[2][3] 就表示从1号顶点到2号顶点,再通过2–>3这条边,到达3号顶点的路程。

dis[3] = 12 , dis[2] + e[2][3] = 1 + 9 = 10   ,dis[3] > dis[2] + e[2][3] ,因此dis[3] 要更新为10,这个过程我们成为“松弛”,1号顶点到3号顶点的路程即dis[3] , 通过2–>3这条边松弛成功。

这就是dijkstra的主要思想:通过“边”来松弛1号顶点到其余各个顶点的路程。

   同理,我们可以通过2–>4(e[2][4]),我们可以将dis[4]的值从∞ 松弛为4(dis[4]初始为∞,dis[2] + e[2][4] = 1 + 3 = 4 , dis[4] > dis[2] + e[2][4] , 因此dis[4]的更新为4)

   我们对2号顶点松弛之后的dis数组为:

最短路Dijkstra算法讲解

 

我们对4号顶点的所有边(4 — > 3 , 4 –> 5 和 4–>6)还用刚才的方法进行松弛,松弛之后为:

最短路Dijkstra算法讲解

接下来对3号顶点的所有出边(3–>5)进行松弛,松弛之后的dis数组为:

最短路Dijkstra算法讲解

 

对5号顶点的所有出边(5 –> 4)进行松弛,松弛完毕的dis数组为:

最短路Dijkstra算法讲解

最后对6号顶点的所有出边进行松弛,得到最终的dis数组,这就是1号到所有点的最短路径:

最短路Dijkstra算法讲解

         我们来对上边的算法来进行一个总结,上述的算法的思想是:每次找到离源点(上述例子的源点就是1号顶点)最近的一个点,然后以该顶点为中心进行扩展,最终得到源点到其他点的最短路径。

完整的dijkstra的算法代码如下:

#include<iostream>
#include<cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1009;
int e[MAXN][MAXN];
 
int main()
{
    int dis[MAXN] , book[MAXN] ;
    int n , m , t1 , t2 , t3 , u , v , mi;
    while(cin >> n >> m)   //n??????,m??????
    {
        for(int i = 1 ; i <= n ; i ++)   //???
        {
            for(int j = 1 ; j<= n ; j ++)
            {
                if(i == j)
                    e[i][j] = 0;
                else
                    e[i][j] = INF;
            }
        }
 
        for(int i = 1 ; i <= m ; i ++)
        {
            cin >> t1 >> t2 >> t3;
            e[t1][t2] = t3;
        }
 
        for(int i = 1 ; i <= n ; i ++) //???dis??,???1?????????????
        {
            dis[i] = e[1][i];
        }
 
        //book ??????
        for(int i = 1 ; i <= n ; i ++)
            book[i] = 0;
        book[1] = 0;
 
        //dijkstra???????
        for(int i = 1 ; i <= n ; i ++)
        {
            //????1???????
            mi = INF;
            for(int j = 1 ; j <= n ; j ++)
            {
                if(book[j] == 0 && dis[j] < mi)
                {
                    mi = dis[j];
                    u = j;
                }
            }
            book[u] = 1;
            for(int v = 1 ; v <= n ; v ++)
            {
                if(e[u][v] < INF)
                {
                    if(dis[v] > dis[u] + e[u][v])
                        dis[v] = dis[u] + e[u][v];
                }
            }
        }
        //???????
        for(int i = 1 ; i <= n ; i ++)
        {
            cout<<dis[i]<<" ";
        }
    }
    return 0 ;
}
/*
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
0 1 8 4 13 17
*/

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114872.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • ViewStub和Gone区别[通俗易懂]

    ViewStub和Gone区别[通俗易懂]虽然把View的初始可见View.GONE但是在Inflate布局的时候View仍然会被Inflate,也就是说仍然会创建对象,会被实例化,会被设置属性。也就是说,会耗费内存等资源。   推荐的做法是使用android.view.ViewStub,ViewStub是一个轻量级的View,它一个看不见的,不占布局位置,占用资源非常小的控件。可以为ViewStub指定一个布局,在Infl

  • 在PyCharm下使用Jupyter Notebook[通俗易懂]

    在PyCharm下使用Jupyter Notebook[通俗易懂]在PyCharm中新建JupyterNotebook文件步骤:File->New…->JupyterNotebook->输入文件名建好之后效果如下图所示,熟悉的JupyterNotebook输入代码,点击绿色三角图标,运行,出现窗口如下:点击“Cancel”取消,点击左下角的“Terminal”,输入“Jupyter-notebook”…

  • 动态代理

    动态代理

  • EXCEL利用VBA把汉字转拼音(李晓锋版)20180828更新「建议收藏」

    EXCEL利用VBA把汉字转拼音(李晓锋版)20180828更新「建议收藏」EXCEL利用VBA把汉字转换为拼音,现在网络中广泛传播的代码存在错误,经过本人严格校对,把修正后的代码分享给大家。代码更新20180607:根据评论,之前的代码的确是无法翻译“瑜琦钰奕”这四个字的拼音,原因是他们的码值没有包含在代码中,现在已添加相应代码。谢谢 likewam  的评论。另外,希望大家能把自己使用过程中发现的所有不能转换的汉字都添加到评论,让我们一起来完善这部分代…

  • HTML+CSS制作二级菜单栏

    HTML+CSS制作二级菜单栏今天我们来练习一下二级菜单栏,说实话比较简单,但是自己一个人写的时候错误百出,逻辑混乱,于是乎网上找了几个案例,借鉴了一下思路,才整明白,鄙人确实不才,哈哈!效果图附上:首先:我已链接了外部样式重置,所以无需自己亲自写:reset.css网上有很多,我用的是下面这个,免费分享给大家,永久有效哦!链接:https://pan.baidu.com/s/1doPA17vy–Qt…

  • 带宽计算_家庭宽带100兆够用吗

    带宽计算_家庭宽带100兆够用吗许多人对Kbps、KB、Mbps等速度单位有所误解,以下简单解释一下所谓的1.5M、3M、6M如何计算。所谓1.5M宽带,其实是指1.5Mbps(bitspersecond),亦

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号