如何找到加权图中是否有一条以上的最短路径

Question

我有一个无向加权图。

我正在使用Dijkstra的算法来找到从源节点到目的节点的最短路径。

但我也想做一个布尔函数，它可以告诉我是否有不止一条最短路径。

我写的代码到现在

#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,source;
cin >> n >> m;
vector<pair<int,int> > g[n+1];  // 1-indexed adjacency list for of graph
int a,b,wt;
for(int i = 0; i<m ; i++){
cin >> a >> b >> wt;
g[a].push_back(make_pair(b,wt));
g[b].push_back(make_pair(a,wt));
}   

cin >> source;

// Dijkstra's algorithm begins from here
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;// min-heap ; In pair => (dist,from)
vector<int> distTo(n+1,INT_MAX);    // 1-indexed array for calculating shortest paths; 

distTo[source] = 0;
pq.push(make_pair(0,source));   // (dist,from)

while( !pq.empty() ){
int dist = pq.top().first;
int prev = pq.top().second;
pq.pop();

vector<pair<int,int> >::iterator it;
for( it = g[prev].begin() ; it != g[prev].end() ; it++){
int next = it->first;
int nextDist = it->second;
if( distTo[next] > distTo[prev] + nextDist){
distTo[next] = distTo[prev] + nextDist;
pq.push(make_pair(distTo[next], next));
}
}

}

cout << "The distances from source, " << source << ", are : n";
for(int i = 1 ; i<=n ; i++) cout << distTo[i] << " ";
cout << "n";

return 0;
}

我不需要不同最短路径中的路径，只需要一个真或假。

我读了很多关于这方面的在线来源，从那里我得到了在算法中没有条件当

if( distTo[next] == distTo[prev] + nextDist)

因此，当这种情况发生时，我应该将该节点添加到列表/2d向量中。

我无法实现这个想法，所以当存在==条件时，我应该将该节点添加到什么？我必须追踪整个路径，然后将其与最短路径进行比较吗？

如果可能的话，你能写代码并向我展示如何做到这一点吗？

我和Dijkstra一起做这件事是不是搞错了？有什么不同的算法可以帮助我做到这一点吗？如果源节点和目标节点之间有一个或多个最短路径，我只需要一个true和false。

更新

示例输入

4,4
0,1,3
1,2,1 
2,3,2 
0,2,4

源-0

目的地-3

为此，destTo矢量输出为0 3 4 6

Answer 1

您可以使用修改后的Dijkstra来跟踪节点是否可以通过多条最短路径到达。

最简单的方法是使用bool:的容器

vector<bool> multipath(n, false);

以及一些管理这些位的逻辑：

if( distTo[next] == distTo[prev] + nextDist){
multipath[next] = true;
}
if( distTo[next] > distTo[prev] + nextDist){
distTo[next] = distTo[prev] + nextDist;
if(multipath[prev])
multipath[next]=true;
pq.push(make_pair(distTo[next], next));
}

然后以某种方式报告结果：

for(int i = 1 ; i<n ; i++){
cout << distTo[i];
if(multipath[i])
cout << "*";
cout << " ";
}
cout << "n";