最短路線修改

-1

有沒有辦法修改這個來顯示最短路徑的路線？例如，如果我有一個像（3,1），（3,0），（4,3），（2,1）這樣的數字列表，則從4到1的輸出將是4> 3,3 - > 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]); 
    }

在存儲像4,3,3,1（使用上面的例子）的路徑的數量的陣列把似乎是最好的辦法，但我不知道在何處插入所述陣列在這個代碼中做到這一點。

來源

2016-11-29 Phoenix Holmes

就像您爲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"); 
}

來源

2016-11-29 21:00:55

聽起來像一個家庭作業問題。

如果這是一個DFS，那麼存儲路徑數字的想法會很棒。不幸的是，Djikstra的算法並不像DFS那樣自然地追蹤路徑;它只需要下一個最近的節點並更新距離值。在這方面它可能更類似於BFS。

你可以做的是當你更新到每個節點的距離，以某種方式存儲你來自哪個節點（也許在你的iPair結構，如果你被允許，也許在地圖/數組，如果你有方式來識別你的節點）。爲了這篇文章，我將它稱爲「from」引用。然後，每次找到節點的較短路徑時，也可以從引用更新該路徑。

那麼您如何找到給定節點的路徑呢？簡單：只需在結束節點處開始，然後按照「從」參考返回源。

來源

2016-11-29 20:54:55

最短路線修改

回答

相關問題