[알고리즘] 플로이드-워셜 알고리즘

---

플로이드-워셜 알고리즘

(Floyd-Warshall Algorithm)

 

간선 weight가 음수 또는 양수인 그래프에서 최단 경로를 찾는데 사용하는 알고리즘

이 알고리즘을 한 번 수행하면 vertex 와 vertex 를 잇는 모든 경우의 수에 대한 최단 거리를 찾을 수 있다.

 

불필요한 글 더 적지 않고 작성한 Python 알고리즘 코드 분석하겠다.

디테일한 문제 상황은 백준의 11404번을 참조하기 바란다.

11404번: 플로이드

 

1부터 n까지의 node가 존재하고

하나의 노드에서 다른 노드로 갈 수 있는 모든 경우의 수에 대해

최단 거리 matrix를 반환해야한다.

갈 수 없는 노드에 대해서는 0을 출력한다.

입력으로 노드 개수(n)와 간선 개수(m)

각 간선의 출발 노드와 도착 노드, weight 값이 제공된다.

 

 

adjacency matrix를 구현하고

이를 플로이드 워셜 알고리즘을 통해

모든 가능한 노드 쌍(start node, terminal node)에 대해

최단 weight를 업데이트한다.

 

여러 문제에서 자주 등장하는 중요한 알고리즘이다.

음의 weight도 처리할 수 있다는 장점이 있고, 

 

하나의 node에서 출발하여

도달할 수 있는 모든 노드에 대해 최단 거리를 찾는 다익스트라에 비해서

2차원 리스트에 표현되는 가능한 모든 노드 pair에 대해 최단 거리를 찾는다는 장점이 있다.