최단 경로 수정

Question

최단 경로 경로를 표시하도록 수정하는 방법이 있습니까? 예를 들어, (3,1), (3,0), (4,3), (2,1)과 같은 숫자 목록이있는 경우 4에서 1로 갈 때의 출력은 4-> 3,3이됩니다. - (위의 예 사용) 4,3,3,1 같은 경로의 수를 저장하는 배열에 넣기> 1

// Prints shortest paths from src to all other vertices 
void Graph::shortestPath(int src) 
{ 
    // Create a priority queue to store vertices that 
    // are being preprocessed. This is weird syntax in C++. 
    // Refer below link for details of this syntax 
    // http://geeksquiz.com/implement-min-heap-using-stl/ 
    priority_queue< iPair, vector <iPair> , greater<iPair> > pq; 


    // Create a vector for distances and initialize all 
    // distances as infinite (INF) 
    vector<int> dist(V, INF); 

    // Insert source itself in priority queue and initialize 
    // its distance as 0. 
    pq.push(make_pair(0, src)); 
    dist[src] = 0; 

    /* Looping till priority queue becomes empty (or all 
     distances are not finalized) */ 
    while (!pq.empty()) 
    { 
     // The first vertex in pair is the minimum distance 
     // vertex, extract it from priority queue. 
     // vertex label is stored in second of pair (it 
     // has to be done this way to keep the vertices 
     // sorted distance (distance must be first item 
     // in pair) 
     int u = pq.top().second; 
     pq.pop(); 

     // 'i' is used to get all adjacent vertices of a vertex 
     list< pair<int, int> >::iterator i; 
     for (i = adj[u].begin(); i != adj[u].end(); ++i) 
     { 
      // Get vertex label and weight of current adjacent 
      // of u. 
      int v = (*i).first; 
      int weight = (*i).second; 

      // If there is shorted path to v through u. 
      if (dist[v] > dist[u] + weight) 
      { 
       // Updating distance of v 
       dist[v] = dist[u] + weight; 
       pq.push(make_pair(dist[v], v)); 
      } 
     } 
    } 

    // Print shortest distances stored in dist[] 
    printf("Vertex Distance from Source\n"); 
    for (int i = 0; i < V; ++i) 
      printf("%d \t\t %d\n", i, dist[i]); 
    } 

는 좋은 생각 같아하지만 난 어디 배열을 삽입하는 방법 모른다 이 코드에서 그렇게 할 수 있습니다.

Answer 1

dist 벡터의 각 정점에 대한 거리를 저장하는 것처럼 마지막으로 업데이트 한 선행 정점을 predecessor이라는 벡터에 저장하십시오. 당신은 전임자의 거리를 업데이트 업데이트 할 때마다 다음

vector<int> dist(V, INF); 
vector<int> predecessor(V, 0); 

: 마지막으로

dist[v] = dist[u] + weight; 
predecessor[v] = u; 

을, 당신이 어떤 정점의 소스에 최단 경로 (뒤로) 추적 할 수 있습니다 :

printf("Vertex Distance from Source  shortest path from source\n"); 
for (int i = 0; i < V; ++i) 
{ 
     printf("%d \t\t %d\t\t", i, dist[i]); 
     int j = i; 
     do 
     { 
      printf("%d,", j); 
      j = predecessor[j]; 
     } while(j != src); 
     printf("\n"); 
} 

을

Answer 2

소리가 숙제 문제와 같습니다.

DFS 인 경우 경로 번호를 저장하는 것이 좋습니다. 불행히도, Djikstra의 알고리즘은 DFS처럼 경로를 자연적으로 추적하지 않습니다. 단순히 다음에 가장 가까운 노드를 취하여 거리 값을 업데이트합니다. 아마도 BFS와 더 유사 할 것입니다.

당신이 할 수있는 일은 각 노드에 대한 거리를 업데이트 할 때 어떤 노드에서 왔는지를 저장하는 것입니다 (어쩌면지도/배열에 허용 된 경우 iPair 구조체에있을 수 있습니다. 노드를 ID로 지정하는 방법). 나는이 게시물을 위해 "from"참조라고 부를 것이다. 그런 다음 노드에 대한 더 짧은 경로를 찾을 때마다 참조에서 업데이트 할 수도 있습니다.

그러면 주어진 노드의 경로를 어떻게 알 수 있습니까? 간단합니다 : 끝 노드에서 시작하여 소스의 "from"참조를 따릅니다.