플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 경로상의 최단거리를 구하는 알고리즘입니다.
다익스트라의 경우 가중치값이 음수가 되는경우 처리하지 못하나 음의 경우에도 처리할 수 있는 특징이 있습니다.
 이 알고리즘은 3개의 루프를 돌게 됩니다.
제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이 됩니다.

루프가 3번 돌아서 시간 복잡도는 O(N^3) 형태를 지닙니다.


한글 wiki 쪽의 경로 부분이 영문과 조금 다른데 빨간색으로 표시한 부분, 영문쪽이 맞는것 같습니다.
한글 wiki
https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

1 procedure floyd-warshall(두 정점을 잇는 모서리의 가중치 테이블 W)
2     D : 두 정점을 잇는 경로의 최소 비용 테이블. 모든 성분을 ∞로 초기화
3     M : 두 정점을 지나가는 최소 비용 경로가 거쳐야 할 마지막 경유지 테이블. 모든 성분을 null로 초기화
4     for i from 1 to |V|
5         for j from 1 to |V|
6             D[i][j] := W[i][j]
7     for v from 1 to |V|
8         D[v][v] := 0
9     for k from 1 to |V|
10        for i from 1 to |V|
11            for j from 1 to |V|
12                if D[i][j] > D[i][k] + D[k][j]
13                    D[i][j] := D[i][k] + D[k][j]
14                    M[i][j] := k
15    return D

영문 wiki
https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
let next be a |V| × |V| array of vertex indices initialized to null

procedure FloydWarshallWithPathReconstruction ()
   for each edge (u,v)
      dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
      next[u][v] ← v
   for k from 1 to |V| // standard Floyd-Warshall implementation
      for i from 1 to |V|
         for j from 1 to |V|
            if dist[i][k] + dist[k][j] < dist[i][j] then
               dist[i][j] ← dist[i][k] + dist[k][j]
               next[i][j] ← next[i][k]

procedure Path(u, v)
   if next[u][v] = null then
       return []
   path = [u]
   while u ≠ v
       u ← next[u][v]
       path.append(u)
   return path


예제는 다익스트라에서 사용했던 예제를 사용하도록 하겠습니다.

소스 코드는 아래와 같습니다.

 path를 관리하기위해서 next 배열을 사용하였습니다 next[i][j]는 i시작 정점이고 j는 도착정점 값은 도착정점을 넣습니다.
예제에서 k=0이면 초기값 상태입니다. tree의 가중치값을 출력하게됩니다.
k=1은 1번 정점을 거쳐가는 모든 node에 대해서 갱신이 일어납니다.


C, pasted just now:

#include <stdio.h> #define MAXN 8 #define MAXV 100 #define DEBUG 1 #define WITHPATH 1 int dist[MAXN+1][MAXN+1]; #if WITHPATH int next[MAXN+1][MAXN+1]; #endif #if DEBUG int debugdist[MAXN+1][MAXN+1]; debuginit() { int N = MAXN; int i,j; for(i=1;i<=N;i++) for(j=1;j<=N;j++) debugdist[i][j]=0; } #endif printdist() { int N = MAXN; int i,j; for(i=1;i<=N;i++) for(j=1;j<=N;j++) if(dist[i][j]!=MAXV && i!=j){ if(debugdist[i][j]){ printf("C "); } #if WITHPATH printf("%d->%d=%d,next %d\n",i,j,dist[i][j],next[i][j]); #else printf("%d->%d=%d\n",i,j,dist[i][j]); #endif } debuginit(); } main() { int N = MAXN; int i,j,k; for(i=1;i<=N;i++) for(j=1;j<=N;j++){ dist[i][j]=MAXV; } for(i=1;i<=N;i++) dist[i][i]=0; dist[1][2]=dist[2][1]=1;next[1][2]=2;next[2][1]=1; dist[1][5]=dist[5][1]=7;next[1][5]=5;next[5][1]=1; dist[1][3]=dist[3][1]=2;next[1][3]=3;next[3][1]=1; dist[2][4]=dist[4][2]=2;next[2][4]=4;next[4][2]=2; dist[2][7]=dist[7][2]=4;next[2][7]=7;next[7][2]=2; dist[3][6]=dist[6][3]=5;next[3][6]=6;next[6][3]=3; dist[4][7]=dist[7][4]=1;next[4][7]=7;next[7][4]=4; dist[5][6]=dist[5][6]=3;next[5][6]=6;next[6][5]=5; dist[5][7]=dist[5][7]=2;next[5][7]=7;next[7][5]=5; dist[6][8]=dist[8][6]=2;next[6][8]=8;next[8][6]=6; dist[7][8]=dist[8][7]=6;next[7][8]=8;next[8][7]=7; #if DEBUG printf("k=%d\n",0); printdist(); debuginit(); #endif // Do Floyd-Warshall Algorithm for (k = 1; k <= N; ++k) { for (i = 1; i <= N; ++i) { for (j = 1; j <= N; ++j) { if (dist[i][j] > dist[i][k] + dist[k][j]) { dist[i][j] = dist[i][k] + dist[k][j]; #if WITHPATH next[i][j] = next[i][k]; #endif #if DEBUG debugdist[i][j]=1; #endif } } } #if DEBUG printf("k=%d\n",k); printdist(); #endif } #if WITHPATH { int path; int start = 1, end=8; printf("Result:%d->%d,Value:%d,",start,end,dist[start][end]); path = next[start][end]; printf("%d",path); for(;;){ if(path==end) break; path = next[path][end]; printf("->%d",path); } printf("\n"); } #endif return 0; }

Output:

k=0 1->2=1,next 2 1->3=2,next 3 1->5=7,next 5 2->1=1,next 1 2->4=2,next 4 2->7=4,next 7 3->1=2,next 1 3->6=5,next 6 4->2=2,next 2 4->7=1,next 7 5->1=7,next 1 5->6=3,next 6 5->7=2,next 7 6->3=5,next 3 6->8=2,next 8 7->2=4,next 2 7->4=1,next 4 7->8=6,next 8 8->6=2,next 6 8->7=6,next 7 k=1 1->2=1,next 2 1->3=2,next 3 1->5=7,next 5 2->1=1,next 1 C 2->3=3,next 1 2->4=2,next 4 C 2->5=8,next 1 2->7=4,next 7 3->1=2,next 1 C 3->2=3,next 1 C 3->5=9,next 1 3->6=5,next 6 4->2=2,next 2 4->7=1,next 7 5->1=7,next 1 C 5->2=8,next 1 C 5->3=9,next 1 5->6=3,next 6 5->7=2,next 7 6->3=5,next 3 6->8=2,next 8 7->2=4,next 2 7->4=1,next 4 7->8=6,next 8 8->6=2,next 6 8->7=6,next 7 k=2 1->2=1,next 2 1->3=2,next 3 C 1->4=3,next 2 1->5=7,next 5 C 1->7=5,next 2 2->1=1,next 1 2->3=3,next 1 2->4=2,next 4 2->5=8,next 1 2->7=4,next 7 3->1=2,next 1 3->2=3,next 1 C 3->4=5,next 1 3->5=9,next 1 3->6=5,next 6 C 3->7=7,next 1 C 4->1=3,next 2 4->2=2,next 2 C 4->3=5,next 2 C 4->5=10,next 2 4->7=1,next 7 5->1=7,next 1 5->2=8,next 1 5->3=9,next 1 C 5->4=10,next 1 5->6=3,next 6 5->7=2,next 7 6->3=5,next 3 6->8=2,next 8 C 7->1=5,next 2 7->2=4,next 2 C 7->3=7,next 2 7->4=1,next 4 C 7->5=12,next 2 7->8=6,next 8 8->6=2,next 6 8->7=6,next 7 k=3 1->2=1,next 2 1->3=2,next 3 1->4=3,next 2 1->5=7,next 5 C 1->6=7,next 3 1->7=5,next 2 2->1=1,next 1 2->3=3,next 1 2->4=2,next 4 2->5=8,next 1 C 2->6=8,next 1 2->7=4,next 7 3->1=2,next 1 3->2=3,next 1 3->4=5,next 1 3->5=9,next 1 3->6=5,next 6 3->7=7,next 1 4->1=3,next 2 4->2=2,next 2 4->3=5,next 2 4->5=10,next 2 C 4->6=10,next 2 4->7=1,next 7 5->1=7,next 1 5->2=8,next 1 5->3=9,next 1 5->4=10,next 1 5->6=3,next 6 5->7=2,next 7 C 6->1=7,next 3 C 6->2=8,next 3 6->3=5,next 3 C 6->4=10,next 3 C 6->5=14,next 3 C 6->7=12,next 3 6->8=2,next 8 7->1=5,next 2 7->2=4,next 2 7->3=7,next 2 7->4=1,next 4 7->5=12,next 2 C 7->6=12,next 2 7->8=6,next 8 8->6=2,next 6 8->7=6,next 7 k=4 1->2=1,next 2 1->3=2,next 3 1->4=3,next 2 1->5=7,next 5 1->6=7,next 3 C 1->7=4,next 2 2->1=1,next 1 2->3=3,next 1 2->4=2,next 4 2->5=8,next 1 2->6=8,next 1 C 2->7=3,next 4 3->1=2,next 1 3->2=3,next 1 3->4=5,next 1 3->5=9,next 1 3->6=5,next 6 C 3->7=6,next 1 4->1=3,next 2 4->2=2,next 2 4->3=5,next 2 4->5=10,next 2 4->6=10,next 2 4->7=1,next 7 5->1=7,next 1 5->2=8,next 1 5->3=9,next 1 5->4=10,next 1 5->6=3,next 6 5->7=2,next 7 6->1=7,next 3 6->2=8,next 3 6->3=5,next 3 6->4=10,next 3 6->5=14,next 3 C 6->7=11,next 3 6->8=2,next 8 C 7->1=4,next 4 C 7->2=3,next 4 C 7->3=6,next 4 7->4=1,next 4 C 7->5=11,next 4 C 7->6=11,next 4 7->8=6,next 8 8->6=2,next 6 8->7=6,next 7 k=5 1->2=1,next 2 1->3=2,next 3 1->4=3,next 2 1->5=7,next 5 1->6=7,next 3 1->7=4,next 2 2->1=1,next 1 2->3=3,next 1 2->4=2,next 4 2->5=8,next 1 2->6=8,next 1 2->7=3,next 4 3->1=2,next 1 3->2=3,next 1 3->4=5,next 1 3->5=9,next 1 3->6=5,next 6 3->7=6,next 1 4->1=3,next 2 4->2=2,next 2 4->3=5,next 2 4->5=10,next 2 4->6=10,next 2 4->7=1,next 7 5->1=7,next 1 5->2=8,next 1 5->3=9,next 1 5->4=10,next 1 5->6=3,next 6 5->7=2,next 7 6->1=7,next 3 6->2=8,next 3 6->3=5,next 3 6->4=10,next 3 6->5=14,next 3 6->7=11,next 3 6->8=2,next 8 7->1=4,next 4 7->2=3,next 4 7->3=6,next 4 7->4=1,next 4 7->5=11,next 4 7->6=11,next 4 7->8=6,next 8 8->6=2,next 6 8->7=6,next 7 k=6 1->2=1,next 2 1->3=2,next 3 1->4=3,next 2 1->5=7,next 5 1->6=7,next 3 1->7=4,next 2 C 1->8=9,next 3 2->1=1,next 1 2->3=3,next 1 2->4=2,next 4 2->5=8,next 1 2->6=8,next 1 2->7=3,next 4 C 2->8=10,next 1 3->1=2,next 1 3->2=3,next 1 3->4=5,next 1 3->5=9,next 1 3->6=5,next 6 3->7=6,next 1 C 3->8=7,next 6 4->1=3,next 2 4->2=2,next 2 4->3=5,next 2 4->5=10,next 2 4->6=10,next 2 4->7=1,next 7 C 4->8=12,next 2 5->1=7,next 1 5->2=8,next 1 C 5->3=8,next 6 5->4=10,next 1 5->6=3,next 6 5->7=2,next 7 C 5->8=5,next 6 6->1=7,next 3 6->2=8,next 3 6->3=5,next 3 6->4=10,next 3 6->5=14,next 3 6->7=11,next 3 6->8=2,next 8 7->1=4,next 4 7->2=3,next 4 7->3=6,next 4 7->4=1,next 4 7->5=11,next 4 7->6=11,next 4 7->8=6,next 8 C 8->1=9,next 6 C 8->2=10,next 6 C 8->3=7,next 6 C 8->4=12,next 6 C 8->5=16,next 6 8->6=2,next 6 8->7=6,next 7 k=7 1->2=1,next 2 1->3=2,next 3 1->4=3,next 2 1->5=7,next 5 1->6=7,next 3 1->7=4,next 2 1->8=9,next 3 2->1=1,next 1 2->3=3,next 1 2->4=2,next 4 2->5=8,next 1 2->6=8,next 1 2->7=3,next 4 C 2->8=9,next 4 3->1=2,next 1 3->2=3,next 1 3->4=5,next 1 3->5=9,next 1 3->6=5,next 6 3->7=6,next 1 3->8=7,next 6 4->1=3,next 2 4->2=2,next 2 4->3=5,next 2 4->5=10,next 2 4->6=10,next 2 4->7=1,next 7 C 4->8=7,next 7 C 5->1=6,next 7 C 5->2=5,next 7 5->3=8,next 6 C 5->4=3,next 7 5->6=3,next 6 5->7=2,next 7 5->8=5,next 6 6->1=7,next 3 6->2=8,next 3 6->3=5,next 3 6->4=10,next 3 6->5=14,next 3 6->7=11,next 3 6->8=2,next 8 7->1=4,next 4 7->2=3,next 4 7->3=6,next 4 7->4=1,next 4 7->5=11,next 4 7->6=11,next 4 7->8=6,next 8 8->1=9,next 6 C 8->2=9,next 7 8->3=7,next 6 C 8->4=7,next 7 8->5=16,next 6 8->6=2,next 6 8->7=6,next 7 k=8 1->2=1,next 2 1->3=2,next 3 1->4=3,next 2 1->5=7,next 5 1->6=7,next 3 1->7=4,next 2 1->8=9,next 3 2->1=1,next 1 2->3=3,next 1 2->4=2,next 4 2->5=8,next 1 2->6=8,next 1 2->7=3,next 4 2->8=9,next 4 3->1=2,next 1 3->2=3,next 1 3->4=5,next 1 3->5=9,next 1 3->6=5,next 6 3->7=6,next 1 3->8=7,next 6 4->1=3,next 2 4->2=2,next 2 4->3=5,next 2 4->5=10,next 2 C 4->6=9,next 7 4->7=1,next 7 4->8=7,next 7 5->1=6,next 7 5->2=5,next 7 5->3=8,next 6 5->4=3,next 7 5->6=3,next 6 5->7=2,next 7 5->8=5,next 6 6->1=7,next 3 6->2=8,next 3 6->3=5,next 3 C 6->4=9,next 8 6->5=14,next 3 C 6->7=8,next 8 6->8=2,next 8 7->1=4,next 4 7->2=3,next 4 7->3=6,next 4 7->4=1,next 4 7->5=11,next 4 C 7->6=8,next 8 7->8=6,next 8 8->1=9,next 6 8->2=9,next 7 8->3=7,next 6 8->4=7,next 7 8->5=16,next 6 8->6=2,next 6 8->7=6,next 7 Result:1->8,Value:9,3->6->8

좀 더 간단한 예제입니다.

                  (1)  --------1------   (2)
                  |                               |
                  1                             1
                  |                               |
                 (3)   --------10------  (4)



C, pasted 1 second ago:

#include <stdio.h> #define MAXN 8 #define MAXV 100 #define DEBUG 1 #define WITHPATH 1 int dist[MAXN+1][MAXN+1]; #if WITHPATH int next[MAXN+1][MAXN+1]; #endif int N = MAXN; #if DEBUG int debugdist[MAXN+1][MAXN+1]; debuginit() { int i,j; for(i=1;i<=N;i++) for(j=1;j<=N;j++) debugdist[i][j]=0; } #endif printdist() { int i,j; for(i=1;i<=N;i++) for(j=1;j<=N;j++) if(dist[i][j]!=MAXV && i!=j){ if(debugdist[i][j]){ printf("C "); } #if WITHPATH printf("%d->%d=%d,next %d\n",i,j,dist[i][j],next[i][j]); #else printf("%d->%d=%d\n",i,j,dist[i][j]); #endif } debuginit(); } main() { int i,j,k; int start,end; for(i=1;i<=N;i++) for(j=1;j<=N;j++){ dist[i][j]=MAXV; } for(i=1;i<=N;i++) dist[i][i]=0; #if 0 start = 1; end = 8; N = 8; dist[1][2]=dist[2][1]=1;next[1][2]=2;next[2][1]=1; dist[1][5]=dist[5][1]=7;next[1][5]=5;next[5][1]=1; dist[1][3]=dist[3][1]=2;next[1][3]=3;next[3][1]=1; dist[2][4]=dist[4][2]=2;next[2][4]=4;next[4][2]=2; dist[2][7]=dist[7][2]=4;next[2][7]=7;next[7][2]=2; dist[3][6]=dist[6][3]=5;next[3][6]=6;next[6][3]=3; dist[4][7]=dist[7][4]=1;next[4][7]=7;next[7][4]=4; dist[5][6]=dist[5][6]=3;next[5][6]=6;next[6][5]=5; dist[5][7]=dist[5][7]=2;next[5][7]=7;next[7][5]=5; dist[6][8]=dist[8][6]=2;next[6][8]=8;next[8][6]=6; dist[7][8]=dist[8][7]=6;next[7][8]=8;next[8][7]=7; #endif #if 1 // - 1 - 2 - // 3 ------ 4 N = 4; start = 3; end = 4; dist[1][2]=dist[2][1]=1;next[1][2]=2;next[2][1]=1; dist[1][3]=dist[3][1]=1;next[1][3]=3;next[3][1]=1; dist[2][4]=dist[4][2]=1;next[2][4]=4;next[4][2]=2; dist[3][4]=dist[4][3]=10;next[3][4]=4;next[4][3]=3; #endif #if DEBUG printf("k=%d\n",0); printdist(); debuginit(); #endif // Do Floyd-Warshall Algorithm for (k = 1; k <= N; ++k) { for (i = 1; i <= N; ++i) { for (j = 1; j <= N; ++j) { if (dist[i][j] > dist[i][k] + dist[k][j]) { dist[i][j] = dist[i][k] + dist[k][j]; #if WITHPATH next[i][j] = next[i][k]; #endif #if DEBUG debugdist[i][j]=1; #endif } } } #if DEBUG printf("k=%d\n",k); printdist(); #endif } #if WITHPATH { int path; //int start = 1, end=8; printf("Result:%d->%d,Value:%d,",start,end,dist[start][end]); path = next[start][end]; printf("%d",path); for(;;){ if(path==end) break; path = next[path][end]; printf("->%d",path); } printf("\n"); } #endif return 0; }

Output:

k=0 1->2=1,next 2 1->3=1,next 3 2->1=1,next 1 2->4=1,next 4 3->1=1,next 1 3->4=10,next 4 4->2=1,next 2 4->3=10,next 3 k=1 1->2=1,next 2 1->3=1,next 3 2->1=1,next 1 C 2->3=2,next 1 2->4=1,next 4 3->1=1,next 1 C 3->2=2,next 1 3->4=10,next 4 4->2=1,next 2 4->3=10,next 3 k=2 1->2=1,next 2 1->3=1,next 3 C 1->4=2,next 2 2->1=1,next 1 2->3=2,next 1 2->4=1,next 4 3->1=1,next 1 3->2=2,next 1 C 3->4=3,next 1 C 4->1=2,next 2 4->2=1,next 2 C 4->3=3,next 2 k=3 1->2=1,next 2 1->3=1,next 3 1->4=2,next 2 2->1=1,next 1 2->3=2,next 1 2->4=1,next 4 3->1=1,next 1 3->2=2,next 1 3->4=3,next 1 4->1=2,next 2 4->2=1,next 2 4->3=3,next 2 k=4 1->2=1,next 2 1->3=1,next 3 1->4=2,next 2 2->1=1,next 1 2->3=2,next 1 2->4=1,next 4 3->1=1,next 1 3->2=2,next 1 3->4=3,next 1 4->1=2,next 2 4->2=1,next 2 4->3=3,next 2 Result:3->4,Value:3,1->2->4

다른 예제입니다.

                  (1)  --------10------ (2)
                  |                               |
                  10                           10
                  |                               |
                 (3) ---1---(5)---1----(4)


C, pasted 1 second ago:

#include <stdio.h> #define MAXN 8 #define MAXV 100 #define DEBUG 1 #define WITHPATH 1 int dist[MAXN+1][MAXN+1]; #if WITHPATH int next[MAXN+1][MAXN+1]; #endif int N = MAXN; #if DEBUG int debugdist[MAXN+1][MAXN+1]; debuginit() { int i,j; for(i=1;i<=N;i++) for(j=1;j<=N;j++) debugdist[i][j]=0; } #endif printdist() { int i,j; for(i=1;i<=N;i++) for(j=1;j<=N;j++) if(dist[i][j]!=MAXV && i!=j){ if(debugdist[i][j]){ printf("C "); } #if WITHPATH printf("%d->%d=%d,next %d\n",i,j,dist[i][j],next[i][j]); #else printf("%d->%d=%d\n",i,j,dist[i][j]); #endif } debuginit(); } main() { int i,j,k; int start,end; for(i=1;i<=N;i++) for(j=1;j<=N;j++){ dist[i][j]=MAXV; } for(i=1;i<=N;i++) dist[i][i]=0; #if 0 start = 1; end = 8; N = 8; dist[1][2]=dist[2][1]=1;next[1][2]=2;next[2][1]=1; dist[1][5]=dist[5][1]=7;next[1][5]=5;next[5][1]=1; dist[1][3]=dist[3][1]=2;next[1][3]=3;next[3][1]=1; dist[2][4]=dist[4][2]=2;next[2][4]=4;next[4][2]=2; dist[2][7]=dist[7][2]=4;next[2][7]=7;next[7][2]=2; dist[3][6]=dist[6][3]=5;next[3][6]=6;next[6][3]=3; dist[4][7]=dist[7][4]=1;next[4][7]=7;next[7][4]=4; dist[5][6]=dist[5][6]=3;next[5][6]=6;next[6][5]=5; dist[5][7]=dist[5][7]=2;next[5][7]=7;next[7][5]=5; dist[6][8]=dist[8][6]=2;next[6][8]=8;next[8][6]=6; dist[7][8]=dist[8][7]=6;next[7][8]=8;next[8][7]=7; #endif #if 0 // - 1 - 2 - // 3 ------ 4 N = 4; start = 3; end = 4; dist[1][2]=dist[2][1]=1;next[1][2]=2;next[2][1]=1; dist[1][3]=dist[3][1]=1;next[1][3]=3;next[3][1]=1; dist[2][4]=dist[4][2]=1;next[2][4]=4;next[4][2]=2; dist[3][4]=dist[4][3]=10;next[3][4]=4;next[4][3]=3; #endif #if 1 // - 1 - 2 - // 3 ------ 4 N = 5; start = 3; end = 4; dist[1][2]=dist[2][1]=10;next[1][2]=2;next[2][1]=1; dist[1][3]=dist[3][1]=10;next[1][3]=3;next[3][1]=1; dist[2][4]=dist[4][2]=10;next[2][4]=4;next[4][2]=2; dist[3][5]=dist[5][4]=1;next[3][5]=5;next[5][3]=3; dist[4][5]=dist[5][4]=1;next[4][5]=5;next[5][4]=4; #endif #if DEBUG printf("k=%d\n",0); printdist(); debuginit(); #endif // Do Floyd-Warshall Algorithm for (k = 1; k <= N; ++k) { for (i = 1; i <= N; ++i) { for (j = 1; j <= N; ++j) { if (dist[i][j] > dist[i][k] + dist[k][j]) { dist[i][j] = dist[i][k] + dist[k][j]; #if WITHPATH next[i][j] = next[i][k]; #endif #if DEBUG debugdist[i][j]=1; #endif } } } #if DEBUG printf("k=%d\n",k); printdist(); #endif } #if WITHPATH { int path; //int start = 1, end=8; printf("Result:%d->%d,Value:%d,",start,end,dist[start][end]); path = next[start][end]; printf("%d",path); for(;;){ if(path==end) break; path = next[path][end]; printf("->%d",path); } printf("\n"); } #endif return 0; }

Output:

k=0 1->2=10,next 2 1->3=10,next 3 2->1=10,next 1 2->4=10,next 4 3->1=10,next 1 3->5=1,next 5 4->2=10,next 2 4->5=1,next 5 5->4=1,next 4 k=1 1->2=10,next 2 1->3=10,next 3 2->1=10,next 1 C 2->3=20,next 1 2->4=10,next 4 3->1=10,next 1 C 3->2=20,next 1 3->5=1,next 5 4->2=10,next 2 4->5=1,next 5 5->4=1,next 4 k=2 1->2=10,next 2 1->3=10,next 3 C 1->4=20,next 2 2->1=10,next 1 2->3=20,next 1 2->4=10,next 4 3->1=10,next 1 3->2=20,next 1 C 3->4=30,next 1 3->5=1,next 5 C 4->1=20,next 2 4->2=10,next 2 C 4->3=30,next 2 4->5=1,next 5 5->4=1,next 4 k=3 1->2=10,next 2 1->3=10,next 3 1->4=20,next 2 C 1->5=11,next 3 2->1=10,next 1 2->3=20,next 1 2->4=10,next 4 C 2->5=21,next 1 3->1=10,next 1 3->2=20,next 1 3->4=30,next 1 3->5=1,next 5 4->1=20,next 2 4->2=10,next 2 4->3=30,next 2 4->5=1,next 5 5->4=1,next 4 k=4 1->2=10,next 2 1->3=10,next 3 1->4=20,next 2 1->5=11,next 3 2->1=10,next 1 2->3=20,next 1 2->4=10,next 4 C 2->5=11,next 4 3->1=10,next 1 3->2=20,next 1 3->4=30,next 1 3->5=1,next 5 4->1=20,next 2 4->2=10,next 2 4->3=30,next 2 4->5=1,next 5 C 5->1=21,next 4 C 5->2=11,next 4 C 5->3=31,next 4 5->4=1,next 4 k=5 1->2=10,next 2 1->3=10,next 3 C 1->4=12,next 3 1->5=11,next 3 2->1=10,next 1 2->3=20,next 1 2->4=10,next 4 2->5=11,next 4 3->1=10,next 1 C 3->2=12,next 5 C 3->4=2,next 5 3->5=1,next 5 4->1=20,next 2 4->2=10,next 2 4->3=30,next 2 4->5=1,next 5 5->1=21,next 4 5->2=11,next 4 5->3=31,next 4 5->4=1,next 4 Result:3->4,Value:2,5->4