2

こんにちは、最短パスを見つけるために C Dijkstra のアルゴリズムを実装しましたが、n 個の最短パスを返す必要があります。

私のダイクストラ関数:

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 つの最短パスが返されます。

ありがとうございました。

4

1 に答える 1

1

実際の最短パス S を呼び出すことから始めましょう。n は S 内のリンクの総数です。

ネットワーク構成に応じてパスの順列が大量になる可能性があるため、これは困難です。次の最短パスを作成するには、アルゴリズムをさらに n 回実行し、各頂点を設定する必要があります。 Visited[m] への最短パス = 1 (次の最短パスが S からの同じ頂点のすべてではなくほとんどを使用する場合)。

2 つの最短パスに対してのみこれを実行したい場合は、これは簡単です。これを実行して任意の数の最短経路を取得できるようにしたい場合は、戻って元の経路リンクのそれぞれを Visited に設定すると、計算時間が指数関数的に増加します。

于 2012-05-13T02:55:34.043 に答える