修改Dijkstra算法打印最短路径中的节点

Question

我想知道如何修改这个函数来保存节点的最终最短路径。这是我的教科书的内容，稍加修改。

template <class vType, int size>
void weightedGraphType<vType, size>::shortestPath(vType vertex) {
int i, j;
double minWeight;

for (j = 0; j < gSize; j++) {
    smallestWeight[j] = weights[vertex][j];
}

bool weightFound[size];

for (j = 0; j < gSize; j++) {
    weightFound[j] = false;
}

for (i = 0; i < gSize; i++) {
    int v;
    cout << vertex << " to " << i << endl;
    minWeight = INFINITY;

    for (j = 0; j < gSize; j++) {
        if (!weightFound[j]) {
            if (smallestWeight[j] < minWeight) {
                v = j;
                minWeight = smallestWeight[v];
            }
        }
    }

    weightFound[v] = true;

    for (j = 0; j < gSize; j++) {
        if (!weightFound[j]) {
            if (minWeight + weights[v][j] < smallestWeight[j]) {
                smallestWeight[j] = minWeight + weights[v][j];
            }
        }
    }
} //end for
} //end shortestPath

Answer 1

这里有一个提示：对于每个节点，您知道到达该节点的最小权重。您还可以在到达此节点之前知道“到达此节点的最短路径”来自哪里。

Answer 2

创建数组来记住目标节点的前驱，然后回溯。

这是修改后的 dijkstra 的完整实现

#include<stdlib.h>
#include<set>
#include<iostream>
#include<vector>
#include<list>
#include<limits.h>
using namespace std;
    struct myHeapcmp{
     bool operator()(const pair<int,int> &a,const pair<int,int>&b){
      return a.second<b.second;
     }

    };

typedef list<pair<int,int> > AdjList;
typedef vector<AdjList> Graph;
typedef multiset<pair<int,int>,myHeapcmp>MinHeap;
vector<int> dijkstra(Graph g,int N,int s){
    vector<int>d(N,100);
    vector<int>  predecessor(N);
    d[s] =0;
    vector<int>p(N,-1);
    vector<MinHeap::iterator>HeapPos(N);
    MinHeap h;
    for(int i=0;i<N;i++)
     HeapPos[i] = h.insert(make_pair(i,d[i]));
     MinHeap::iterator it;
    while(h.size()>0){
     it = h.begin();
     int v = it->first;

     h.erase(it);
     AdjList::iterator it2;
     for(it2=g[v].begin();it2!=g[v].end();it2++){
       int u = it2->first;
       int w_uv= it2->second;
       if(d[u]>w_uv+d[v]){
         d[u]= w_uv+d[v];
         predecessor[u] = v;
         p[u]=v; h.erase(HeapPos[u]);
         HeapPos[u]= h.insert(make_pair(u,d[u]));
       }

     }
    }
    for(int i = 0;i<N;i++){
        int node = i;
        int pre = predecessor[i];
        cout<<i<<" :";
        while(pre!=s){
            cout<<pre<<" ";
            node = pre;
            pre = predecessor[node];
        }
        cout<<s<<endl;
    }

 return d;
}

Answer 3

做到这一点的一种方法是引入一个额外的循环，在所有节点上迭代算法，并且使用距离数组，您可以存储“通过节点”元素。
一旦计算出从每个节点到每个其他节点的最短路径，您所要做的就是遵循您存储的“通过节点”值。
顺便说一句，就效率而言，这个算法很糟糕，它是 O(n^3)。