가장 짧은 최단 경로 (dijkstra 알고리즘)를 반환하는 방법

Question

안녕하세요, 저는 C 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.

에있는 링크의 수

이것은 네트워크 구성에 따라 경로의 순열의 톤을 미칠 수 있기 때문에 힘든 될 것입니다 다음에의 최단 경로를 만들려면 다음 최단 경로가 가장 많이 사용하는 경우 최단 경로의 각 꼭짓점을 Visited [m] = 1로 설정하여 각 실행에 대해 알고리즘을 n 번 더 실행해야합니다 . 그러나 동일한 꼭지점을 모두 가지고있는 것은 아닙니다.

두 개의 짧은 경로에 대해서만이 것을 실행하고 싶다면 간단합니다. 이것을 실행하여 임의의 수의 최단 경로를 얻으려면 돌아가서 각 원래 경로 링크를 방문으로 설정하면 계산 시간이 기하 급수적으로 늘어납니다.