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

Question

你好，我已经在 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;
}

我需要调用此函数 2 次，然后返回图中的两条最短路径。

谢谢。

Answer 1

让我们首先调用实际的最短路径 S，n 是 S 中的链接总数。

这会很困难，因为根据网络配置，您可能会有大量路径排列，为了创建下一个最短路径，您必须运行算法 n更多次，为每次运行将最短路径中的每个顶点设置为 Visited[m] = 1，以防下一个最短路径使用最多，但不是所有来自 S 的相同顶点。

如果您真的只想为两条最短路径运行此程序，那么这将很简单。如果您希望能够运行它来获得任意数量的最短路径，那么当您返回并将每个原始路径链接设置为 Visited 时，您的计算时间将成倍增加。