Floyd-Warshall Algorithm

플로이드-워셜 (Floyd-Warshall)

플로이드-워셜 알고리즘은 모든 최단 경로를 구하는 방법이다.

다익스트라 알고리즘은 음의 가중치를 가진 간선은 못쓴다는 제약이 있었다. 하지만 플로이드-워셜에선 사용이 가능하다.

모든 정점에 대한 경로를 계산하므로 거리를 저장할 자료구조는 2차원 배열이 된다. 플로이드-워셜은 optimal substructure의 개념을 이용하여 최단 경로를 찾는다. optimal substructure란 특정 경로 안에 무수히 많은 경로가 있을 때, 중간 정점들이 각각 최단이 된다면 이를 모두 이은 경로 또한 최단이 된다는 개념이다.

Pseudo Code

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u,v)
  dist[u][v] ← w(u,v)  // 변 (u,v)의 가중치
for each vertex v
  dist[v][v] ← 0
for k from 1 to |V|
  for i from 1 to |V|
    for j from 1 to |V|
      if dist[i][j] > dist[i][k] + dist[k][j]
        dist[i][j] ← dist[i][k] + dist[k][j]
      end if

Example