플로이드-와셜 알고리즘

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

표제어를 변경하자는 제안이 있습니다. (토론)

이 문서의 외래어 표기는 외래어 표기법과 다를 수 있습니다.

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

[편집] 소스 코드

[편집] C 언어

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];
      }
    }
  }
}

이 글은 전산학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.