Dijkstra的問題，找到所有最小路徑

Question

我們在這裏有一個問題，我們試圖從一個節點到另一個節點查找圖中所有最短的路徑。我們已經實施了dijkstra，但我們真的不知道如何找到它們。

我們是否必須使用BFS？

#include <vector> 
#include <iostream> 
#include <queue> 
using namespace std; 

typedef pair <int, int> dist_node; 
typedef pair <int, int> edge; 
const int MAXN = 10000; 
const int INF = 1 << 30; 
vector <edge> g[MAXN]; 
int d[MAXN]; 
int p[MAXN]; 

int dijkstra(int s, int n,int t){ 
    for (int i = 0; i <= n; ++i){ 
     d[i] = INF; p[i] = -1; 
    } 
    priority_queue < dist_node, vector <dist_node>,greater<dist_node> > q; 
    d[s] = 0; 
    q.push(dist_node(0, s)); 
    while (!q.empty()){ 
     int dist = q.top().first; 
     int cur = q.top().second; 
     q.pop(); 
     if (dist > d[cur]) continue; 
     for (int i = 0; i < g[cur].size(); ++i){ 
      int next = g[cur][i].first; 
      int w_extra = g[cur][i].second; 
      if (d[cur] + w_extra < d[next]){ 
       d[next] = d[cur] + w_extra; 
       p[next] = cur; 
       q.push(dist_node(d[next], next)); 
      } 
     } 
    } 
    return d[t]; 
} 

vector <int> findpath (int t){ 
    vector <int> path; 
    int cur=t; 
    while(cur != -1){ 
     path.push_back(cur); 
     cur = p[cur]; 
    } 
    reverse(path.begin(), path.end()); 
    return path; 
} 

這是我們的代碼，我們相信我們必須修改它，但我們真的不知道在哪裏。

Answer 1

目前，您只能保存/檢索您碰巧找到的最短路徑之一。考慮下面這個例子：

4 nodes 
0 -> 1 
0 -> 2 
1 -> 3 
2 -> 3 

很清楚，你不能對每個位置的單一p[]價值，其實第4節點（3）有2個以前的有效節點：1和2。

如下你可以這樣用vector<int> p[MAXN];和工作替換：

if (d[cur] + w_extra < d[next]){ 
    d[next] = d[cur] + w_extra; 
    p[next].clear(); 
    p[next].push_back(cur); 
    q.push(dist_node(d[next], next)); 
} 
else if(d[cur] + w_extra == d[next]){ 
    p[next].push_back(cur); // a new shortest way of hitting this same node 
} 

您還需要更新您的findpath()功能，因爲這將需要處理「分支」導致一些多條路徑，可能取決於圖表的指數級數量的路徑。如果你只需要打印的路徑，你可以做這樣的事情：

int answer[MAXN]; 

void findpath (int t, int depth){ 
    if(t == -1){ // we reached the initial node of one shortest path 
     for(int i = depth-1; i >= 0; --i){ 
      printf("%d ", answer[i]); 
     } 
     printf("%d\n", last_node); // the target end node of the search 
     return; 
    } 
    for(int i = p[t].size()-1; i >= 0; --i){ 
     answer[depth] = p[t][i]; 
     findpath(p[t][i], depth+1); 
    } 
} 

注意，你需要在你的Dijkstra的開始做p[s].push_back(-1)，除了清算案件之間的矢量數組。