2

您好，我已经在 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 次，它会返回图中的两条最短路径。

谢谢你。

4

1 回答 1

1

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

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

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

于 2012-05-13T02:55:34.043 回答