如何返回n最佳最短路径（dijkstra算法）

你好我已经在C Dijkstra的算法中实现了找到最短路径，但是我需要返回n个最短路径，任何人都有一个想法我该怎么做。如何返回n最佳最短路径（dijkstra算法）

我的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倍这个函数并返回，图中的两个最短路径。

谢谢。

来源

2012-05-13 Ruben Gonçalves

这是一个功课问题吗？ – gcbenison

不，不是，我正在寻找迪杰斯特拉，我不是在问一个解决方案，只是一些想法，我该怎么做。 –

迭代运行Dijstra，每次删除解决方案的顶点。 – tbert

让我们通过调用实际的最短路径S开头的n是链接在S.

总数

这将是艰难的，因为你可以有一吨取决于网络配置的路径的排列并且为了创建最短路径，您将不得不再次运行算法n，为每次运行将最短路径中的每个顶点设置为Visited [m] = 1，以防下一个最短路径使用最多路径，但不是所有与S相同的顶点。如果你真的只想运行这两个最短路径，那么这将是直截了当的。如果您希望能够运行此项以获取任意数量的最短路径，则在返回时将您的计算时间按指数级增加，并将每个原始路径链接设置为“已访问”。

来源

2012-05-13 02:55:34 MrWuf

我将放置起始顶点和最终顶点，并且必须返回两个顶点之间的两条最短路径。 –

如何返回n最佳最短路径（dijkstra算法）

回答

相关问题