还是以举例子为主吧,部分图片来自于网络。
在下边的学习中,主要是通过松弛操作让最短路的值进行替换。dijie斯特拉指定一个点(源点)到其余的各个顶点的最短路径,也叫做“单源最短路径”。
例如下图中的1号顶点到2,3,4,5,6顶点的最短路径:
在这里要和flody算法一样,在这儿也需要用二维数组e来存取顶点之间和边之间的关系,数值如下:
在这儿我们还需要用一个一维数组dis来存取1号顶点到各个顶点的初始路程,如下:
因为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数组为:
我们对4号顶点的所有边(4 — > 3 , 4 –> 5 和 4–>6)还用刚才的方法进行松弛,松弛之后为:
接下来对3号顶点的所有出边(3–>5)进行松弛,松弛之后的dis数组为:
对5号顶点的所有出边(5 –> 4)进行松弛,松弛完毕的dis数组为:
最后对6号顶点的所有出边进行松弛,得到最终的dis数组,这就是1号到所有点的最短路径:
我们来对上边的算法来进行一个总结,上述的算法的思想是:每次找到离源点(上述例子的源点就是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账号...