플로이드-와셜 알고리즘
위키백과, 우리 모두의 백과사전.
플로이드-와셜 알고리즘(Floyd-Warshall Algorithm})은 그래프에서 모든 정점간의 최단거리를 구하는 알고리즘이다. 음수 간선도 사이클만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 정점이고, 두 번째 반복문은 출발하는 정점, 세 번째 반복문은 도착하는 정점이다. 이 알고리즘은 플로이드 알고리즘이랑은 다르다.
소스 코드 [편집]
C 언어 [편집]
void _back(int i, int j){ if(!b[i][j]){ printf("%d ", i); return; } _back(a, b[i][j]); _back(b[i][j], b); } void back(int i, int j){ _back(i,j); printf("%d\n", j); } void floyd(){ for(int i = 1; i <= N; i++){ for(int j = 1; j <= N; j++){ d[i][j] = w[i][j]; //k=0 } } for(int k = 1; k <= N; k++){ for(int i = 1; i <= N; i++){ for(int j = 1; j <= N; j++){ if(d[i][j] > d[i][k] + d[k][j]){ d[i][j] = d[i][k] + d[k][j]; b[i][j] = k; } } } } }
| 이 글은 컴퓨터 과학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다. |