c - 如何返回n个最佳最短路径(dijkstra算法)

您好，我已经用C Dijkstra的算法实现了寻找最短路径，但是我需要返回n条最短路径，任何人都知道我该怎么做。
我的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;
}

我需要调用eg 2次这个函数，它返回，图中的两条最短路径。
谢谢您。

最佳答案

首先调用实际的最短路径S，n是S中的链接总数。
这将很困难，因为根据网络配置，您可能有大量的路径排列，为了创建下一个最短路径，您将不得不运行算法n次，在下一个最短路径使用最多的情况下，将最短路径中的每个顶点设置为每次访问的[m]=1所有来自S的相同顶点。
如果你真的只想在两条最短的路径上运行这个，那么这将很简单如果您希望能够运行此命令以获得任意数量的最短路径，那么在返回并将每个原始路径链接设置为已访问时，您的计算时间将成倍增加。