如何返回n最佳最短路徑（dijkstra算法）

你好我已經在C Dijkstra的算法中實現了找到最短路徑，但是我需要返回n個最短路徑，任何人都有一個想法我該怎麼做。如何返回n最佳最短路徑（dijkstra算法）

我的Dijkstra功能：

int * Dijkstra(graph **g, int totalVertex, int vStart) { 
    int i; 
    int *distance = (int*) malloc(totalVertex * sizeof (int)); 
    int *last = (int*) malloc(totalVertex * sizeof (int)); 
    int *visited = (int*) calloc(totalVertex, sizeof (int)); 
    int maxDistance, m; 
    graph *vertex; 

    for (i = 0; i < totalVertex; i++) { 
    distance[i] = MAXINT; 
    last[i] = -1; 
    } 

    distance[vOrigem] = 0; 

    while (sum(visited, totalVertex) < totalVertex) { 

    maxDistance = MAXINT; 

     for (i = 0; i < totalVertex; i++) { 
     if ((distance[i] < maxDistance) && (visited[i] == 0)) { 
      maxDistance = distance[i]; 
      m = i; 
     } 
     } 

    vertex = g[m]; 
    while (vertex != NULL) { 
     if ((vertex->distance + distance[m]) < (distance[vertex-> destination])) { 
     distance[vertex->destination] = vertex->distance + distance[m]; 
     last[vertex->destination] = m; 
     } 
    vertex = vertice->next; 
    } 
    visited[m] = 1; 
    } 
    free(distance); 
    free(visited); 
    return last; 
}

我需要調用如2倍這個函數並返回，圖中的兩個最短路徑。

謝謝。

來源

2012-05-13 Ruben Gonçalves

這是一個功課問題嗎？ – gcbenison

不，不是，我正在尋找迪傑斯特拉，我不是在問一個解決方案，只是一些想法，我該怎麼做。 –

迭代運行Dijstra，每次刪除解決方案的頂點。 – tbert

讓我們通過調用實際的最短路徑S開頭的n是鏈接在S.

總數

這將是艱難的，因爲你可以有一噸取決於網絡配置的路徑的排列並且爲了創建最短路徑，您將不得不再次運行算法n，爲每次運行將最短路徑中的每個頂點設置爲Visited [m] = 1，以防下一個最短路徑使用最多路徑，但不是所有與S相同的頂點。如果你真的只想運行這兩個最短路徑，那麼這將是直截了當的。如果您希望能夠運行此項以獲取任意數量的最短路徑，則在返回時將您的計算時間按指數級增加，並將每個原始路徑鏈接設置爲「已訪問」。

來源

2012-05-13 02:55:34 MrWuf

我將放置起始頂點和最終頂點，並且必須返回兩個頂點之間的兩條最短路徑。 –

如何返回n最佳最短路徑（dijkstra算法）

回答

相關問題