Модификация алгоритма Дейкстры для печати узлов по кратчайшему пути

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

Создать массив для запоминания предшественника узла назначения и затем отследить.

Вот полная реализация модифицированного дижкстра

#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).