在dijstra算法中打印路徑

Question

我的cs教授給了我一個dijstras算法的實現，他要求我們修改它以打印從源節點「src」（參見代碼）到每個節點的路徑，以及距離（它已經做到了）。我已經看了大約一個星期了，並嘗試了幾件事情。我無法弄清楚我的生活......任何幫助將不勝感激。該圖由adjecency矩陣表示，有一個全球性的含有它的大小：

int n; //Global matrix's size 
int minDistance(int dist[], bool sptSet[]){ 
    // Initialize min value 
    int min = INT_MAX, min_index; 
    int i = 0; 
    for (i = 0; i < n; i++) 
     if (sptSet[i] == false && dist[i] <= min) 
      min = dist[i], min_index = i; 
    return min_index; 
} 

int printSolution(int dist[]){ 
    printf("Vertex Distance from Source\n"); 
    int i; 
    for (i = 0; i < n; i++) 
     printf("%d \t\t %d\n", i, dist[i]); 
} 

void dijkstra(int ** graph, int src){ 
    //correting zeros (won't work with negative values) 
    correctZeros(graph); 
    int dist[n]; 
    bool sptSet[n]; 
    int i; 
    for (i = 0; i < n; i++) 
     dist[i] = INT_MAX, sptSet[i] = false; 
    dist[src] = 0; 

    // Find shortest path for all vertices 
    int count; 
    for (count = 0; count < n; count++){ 
     int u = minDistance(dist, sptSet); 
     sptSet[u] = true; 
     int j; 
     for (j = 0; j < n; j++){ 
      printf("%d", u); 
      if (!sptSet[j] && graph[u][j] && dist[u] != INT_MAX && dist[u]+graph[u][j] < dist[j]){ 
       dist[j] = dist[u] + graph[u][j]; 

      } 
     } 
    } 
    printSolution(dist); 
} 

Answer 1

所有你需要做的是存儲什麼是最短路徑的下一跳的每個節點。無論何時更新節點的最短路徑的距離，都會更新此信息。

Answer 2

當您執行Relax計算時，使用另一個陣列來存儲前一個節點。

node[src] = src; //init source node 
if (!sptSet[j] && graph[u][j] && dist[u] != INT_MAX && dist[u]+graph[u][j] < dist[j]){ 
      dist[j] = dist[u] + graph[u][j]; 
      node[j] = u; //store previous node step 
     } 

使用一個循環來打印所有節點，直到節點[X] = X（源節點）

printPath(int node[], int i, int src) 
{ 

    int currentNode = i; 
    printf(currentNode); 
    while(currentNode!=src) 
    { 
     printf(node[currentNode]); 
     currentNode = node[currentNode]; 
    } 
} 

我不是很熟悉C語言，所以也許有一些C語法錯誤。謝謝。