dijkstra求最短路并记录路径

2024-07-09 19:01| 来源: 网络整理| 查看: 265

dijkstra算法是单源最短路算法的一种，可用于求从出发节点到所有可到达节点的最短路长度。

下面我们来看下如何记录最短路的路径，有关dijkstra求最短路长度的过程，可以看这篇博客“dijkstra求最短路径长度”。

举例

下图中直接给出记录路径的过程，相比于求解最短路长度，只多了一个path数组（初始化为-1）用于记录路径。

分析

从上图可以看到，从出发节点0到节点5取得最小长度65，所经过的路径是0，3，2，4，5。

图中通过path数组来记录路径，path[i]=j表明节点i取得最小路径时，其最后一段走的是节点j到节点i。

你也许会疑惑，我想知道的是整个路径呀，记录其中的最后一段有什么用呢？

我们这样来看，path[5]=4表明0->5的最短路径最后走的一段是4->5；同理path[4]=2确定0->4的最短路径的最后一段是由节点2到达节点4；那么通过path[2]=3可以得到0->2最短路径最后一段是由节点3到达节点2；而path[3]=-1表示从出发节点0有一条直接路径连接到节点3。在这个过程中，我们获得经过的路径是倒序的，所以给出答案时需要反转，故从出发节点0到节点5所经过的最短路径是0，3，2，4，5。

但你也许又有一个疑问，path[5]=4表明0->5的最短路径最后一段是4->5，可是你怎么知道0->4的最短路径与0->5的最短路径在0->4段走的是相同的路径呢？

首先0->5的最短路径是0，3，2，4，5，path[5]=4表明0->5最短路径的最后一段是4->5，其中4->5必定只有一条直接路径，所以可以推得0->4的最短路径为0，3，2，4；因为如果0->4有更短的路径0->X->4，那么0->5的最短路径必定也会变成0->X->4->5。从图中也可以看到，path[i]并不是一旦赋值就不会改变的；只有i被作为了中途节点，那么path[i]才不会再改变，即出发节点到节点i的最小长度被确定后。

注意：图中初始化时path全为-1，并不是因为其出发节点为-1。比如path[i]=-1表明的是出发节点到节点i是直接路径，没有中途节点；并不代表从节点-1可以到节点i，也不代表-1是出发节点。当然初始值可以任意替换，只要注意更改“while(path[j]!=-1)”即可。

代码实现 #include #include #include using namespace std; const int N=100; const int INF=100000; int p[N][N],d[N],path[N]; //path数组用于记录路径 void dijkstra(int sec,int n) //sec为出发节点，n表示图中节点总数 { int i,j,min,min_num; int vis[N]={0,}; for(i=0;i

【本文地址】

公司简介

联系我们