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

플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 간선 weight가 음수 또는 양수인 그래프에서 최단 경로를 찾는데 사용하는 알고리즘 이 알고리즘을 한 번 수행하면 vertex 와 vertex 를 잇는 모든 경우의 수에 대한 최단 거리를 찾을 수 있다. 불필요한 글 더 적지 않고 작성한 Python 알고리즘 코드 분석하겠다. 디테일한 문제 상황은 백준의 11404번을 참조하기 바란다. 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 1부터 n까지의 node가 존재하고 하나의 노드에서 다른..

원문링크 : [알고리즘] 플로이드-워셜 알고리즘