n最短経路を返す方法（dijkstraアルゴリズム）

Question

こんにちは私はCダイクストラのアルゴリズムで最短経路を見つけましたが、最短経路を返す必要があります。

マイダイクストラ機能：

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つの最短経路、私は2回に例えば、この関数を呼び出す必要があり、それが返されます。

ありがとうございます。

Answer 1

は、実際の最短経路Sを呼び出すことによって開始し、nは、ネットワーク構成に応じてパスの順列のトンを持っている可能性があるため、これは厳しいものになるだろうS.

内のリンクの総数であることができます次のの最短パスを作成するには、最短パスの各頂点を次回の最短パスが最も多く使用される場合の実行ごとにVisited [m] = 1に設定して、アルゴリズムをn回以上実行する必要がありますただし、2つの最短パスでのみ実行したい場合は、これは簡単です。これを実行して、任意の数の最短パスを取得できるようにしたい場合は、元のパスリンクを訪問済みに戻すときに計算時間が急激に増加します。