플로이드-워셜 알고리즘

플로이드-워셜 알고리즘

플로이드-워셜(Floyd-Warshall Algorithm)은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다.

시간 복잡도는 O(n^3)이다. 다익스트라 알고리즘과 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다.

플로이드-워셜 알고리즘은 임의의 노드 s에서 e까지 가는 데 걸리는 최단 거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는데 걸리는 최단 거리와 m에서 e까지 가는데 걸리는 최단거리를 이용한다.

구체적으로 설명하면, 임의의 노드 s 부터 e 까지 가는데 걸리는 최단 거리를 d[s][e] 라고 하자. (처음에 d[s][e]의 값은 노드 s 와 노드 e 가 직접적으로 연결되어 있다면 그 노드의 가중치만큼, 그렇지 않다면 무한(INF)로 초기화한다.) 이 d[s][e] 를 구하기 위해서, s 와 e 사이의 모든 노드 m에 대해, 현재 d[s][e] 에 저장되어 있는 값과 d[s][m] +d[m][e] 의 값을 비교한다. 이 때 d[s][m] + d[m][e] 의 값이 현재의 d[s][e] 값보다 작으면, d[s][e] 를 d[s][m] + d[m][e] 의 값으로 업데이트 한다.

코드

단순히 반복문을 3번 중첩시키기만 하면 되기 때문에 큰 어려움 없이 간결하게 구현할 수 있다. 단, 유의해야 할 점은 for 문에서 가운데 노드(m) 가 제일 위에 있어야 한다는 점이다.

• (상단) 거쳐가는 노드
• (중단) 시작점 노드
• (하단) 도착점 노드

for m in range(1, n+1): # 거쳐가는 노드
    for i in range(1, n+1): # 출발 노드
        for j in range(1, n+1): # 도착 노드
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

코드만 보면, "중간에 여러 노드들을 거쳐갈 수 있는데 왜 가운데 노드를 한개밖에 두지 않는거지?" 라는 물음이 생길 수 있지만, 아래의 동작 과정을 보면 결국 모든 가운데 노드들에 대해 최적의 경로를 고려했다는 것을 알 수 있다.

예시
노드 A, B, C, D 가 있다고 할때, 다음의 정보가 있다고 하자
*위 연결 정보를 제외하고는 연결되어 있지 않음 (INF)

• A -> D = 19
• A -> B = 3
• B -> C = 7
• C -> D = 5

위 코드 방식을 따라가보면

(m 이 A 일때)
거쳐가는 노드가 시작 노드인 경우에는 "이미 그 자체가 포함된 경로" 이기 때문에 추가적인 경유지 역할을 하지 못한다.
즉, 계산은 하지만 아무런 변화가 없다.

(m 이 B 일때)

• A -> B -> C
  dist[A][C] = min(INF, 3 + 7) => 10 (변화 O)
• A -> B -> D
  dist[A][D] = min(19, 3 + INF) => 19 (변화 X)
• C -> B -> D
  dist[C][D] = min(INF, INF + INF) => INF (변화 X)
• C -> B -> A
  dist[C][A] = min(INF, INF + INF) => INF (변화 X)
• D -> B -> A
  dist[D][A] = min(INF, INF + INF) => INF (변화 X)
• D -> B -> C
  dist[D][C] = min(INF, INF + 7) => INF (변화 X)

(m 이 C 일때)

• A -> C -> D
  *dist[A][C] 는 m 가 B 일때 "A->C" 의 비용에서 "A->B->C" 의 비용으로 새로 갱신된 값임
  dist[A][D] = min(19, 10 + 5) => 15 (변화 O)
• A -> C -> B
  dist[A][B] = min(3, 10 + INF) => 3 (변화 X)
• B -> C -> A
  dist[B][A] = min(INF, 7 + INF) => INF (변화 X)
• B -> C -> D
  dist[B][D] = min(INF, 7 + 5) => 12 (변화 O)
• D -> C -> A
  dist[D][A] = min(INF, INF + INF) => INF (변화 X)
• D -> C -> B
  dist[D][B] = min(INF, INF + INF) => INF (변화 X)

(m 이 D 일때)
거쳐가는 노드가 도착 노드인 경우에는 "이미 그 자체가 포함된 경로" 이기 때문에 추가적인 경유지 역할을 하지 못한다.
즉, 계산은 하지만 아무런 변화가 없다.

결론

수식상 보면 k 라는 하나의 중간 노드를 넣어 계산하는 것 같지만,
실제로는 그 k 번째 계산이 이전까지 거쳐온 모든 노드들의 최적 경로 정보를 포함하고 있다.

즉,

• k = 1 -> 노드 1까지 거칠 수 있는 경로 중 최단 경로
• k = 2 -> 노드 1, 2까지 거칠 수 있는 경로 중 최단 경로
• k = 3 -> 노드 1, 2, 3까지 거칠 수 있는 경로 중 최단 경로

이렇게 중간에 거칠 수 있는 노드 집합이 점점 확장되며 계산된다. 따라서, 하나의 중간 노드만 고려하는 것 같아 보여도, 이전 단계까지 누적된 최적의 경로를 기반으로 계산되기 때문에, 결국 모든 가능한 중간 경로를 포함한 최적의 경로를 구할 수 있다.