最短路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)


相关推荐

发表回复

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

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