플로이드-와셜 알고리즘

위키백과 ― 우리 모두의 백과사전.

플로이드-와셜 알고리즘(영어: Floyd-Warshall Algorithm})은 그래프에서 모든 정점간의 최단거리를 구하는 알고리즘이다. 음수 간선도 사이클만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 정점이고, 두번째 반복문은 출발하는 정점, 세번째 반복문은 도착하는 정점이다.

[편집] 소스 코드

for(i=1;i<=N;i++) {
  for(j=1;j<=N;j++) {
    for(k=1;k<=N;k++) {
      if(cost[j][i]+cost[i][k]<cost[j][k]) cost[j][k]=cost[j][i]+cost[i][k];
    }
  }
}