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

이렇게하는 한 가지 방법은 모든 노드에서 알고리즘을 반복하는 하나의 추가 루프를 도입하는 것이며 거리 어레이를 사용하면 "via node"요소를 저장할 수 있습니다. 일단 각 노드에서 다른 모든 노드로 계산 된 최단 경로를 계산하면 저장 한 "via 노드"값을 따라야합니다. btw, 효율 측면에서이 알고리즘은 싫증 나며 O (n^3)입니다.

Answer 3

대상 노드의 선행자를 기억하고 다시 추적하도록 배열을 만듭니다.

여기 최단 경로를 포함하는 노드

#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; 
}