플로이드의 최단 경로 알고리즘 C++

Question

은 내가 목적지에 도달하기 위해 노력하고 다음 노드를 제공하는 경로 행렬을 생성 할 때, 그 제외하고는 제대로 작동 가중 이중 음자에 대한 C에서 플로이드의 알고리즘 ++의 기능을 구현 한 즉시 정점을두고 행렬의 소스에서 다음 노드 대신 대상 앞에옵니다. 거리 매트릭스 (dist)가 올바르게 나오고 소스와 대상 사이에 최대 하나의 노드가 있으면 전체 경로 매트릭스가 정확합니다. 따라서 꼭지점 i에서 j까지의 최단 경로가 길면 path [i] [j]는 i와 연결된 k 값과 같아야합니다. 대신 j와 연결된 k 값은 이유를 파악할 수 없습니다. 이 기능은 아래와 같습니다. 정점에서 긴 최단 경로가 존재 그렇다면

void floyd(const Graph<City>& g, double**& dist, int**& path) 
{ 
    int n = g.size(); 
    for (int i = 1; i <= n; i++) 
    { 
     for (int j = 1; j <= n; j++) 
     { 
      path[i][j]=0; 
      if (i==j) 
       dist[i][j]=0; 
      else if (!g.isEdge(i, j)) 
       dist[i][j]=INFINITY; 
      else 
       dist[i][j]=g.retrieveEdge(i, j); 
     } 
    } 
    for (int i = 1; i <= n; i++) 
    { 
     for (int j = 1; j <= n; j++) 
     { 
      for (int k = 1; k <= n; k++) 
      { 
       if ((dist[i][k]!=INFINITY) && (dist[k][j]!=INFINITY) && k!=i && k!=j && i!=j) 
       { 
        if ((dist[i][j]) > (dist[i][k]+dist[k][j])) 
        { 
         path[i][j]=k; 
         dist[i][j]=dist[i][k]+dist[k][j]; 
        } 
       } 
      } 
     } 
    } 
} 

Answer 1

I J에 다음 경로 [I] [J] AK I 접속 값 대신 그것의 AK 값 J에 접속되고 I 알아낼 수 같아야 왜.

불행하게도 모두. 귀하의 구현에서 path[i][j]이 i 바로 뒤에 오는 k 값과 같아야하고, path[i][j]이 현재 k 값인 관찰이 j 바로 앞에 오도록 보장하는 것도 없습니다. (두 번째 점을 확인하기 위해 더 많은 몇 가지 샘플을 시도하십시오.)

구현에 의해 보장되는 유일한 방법은 정점 path[i][j] == k이 j 버텍스 정점 i에서 최단 경로 어딘가에 놓여 있다는 점이다.

따라서 당신은 수행하여 재귀 적 경로를 검색 할 수 있습니다

get_path(i, j): 
    k = path[i][j] 
    get_path(i, k) + k + get_path(k, j) 

가 명확히 데 당신이 저장할 수 there does exist a method, 그 path[i][j]이 i 직후 오는 정점이되도록.