플로이드–워셜 알고리즘
최단 경로 알고리즘은 보통 한 정점에서 나머지 전부로 가는 거리를 푼다. 다익스트라와 벨만-포드 모두 시작점이 하나다. 모든 정점에서 모든 정점으로 가는 거리가 필요하면 다익스트라를 V번 돌릴 수도 있지만, 우선순위 큐와 인접 리스트를 매번 다시 세팅해야 하고 음수 가중치가 있으면 쓸 수 없다. 플로이드-워셜은 시작점을 고정하지 않는다. 거리 행렬 하나를 놓고 3중 루프를 한 번 돌면 모든 쌍의 최단 거리가 행렬에 채워진다. 코드는 12줄이고, 음수 간선을 처리하며, 음수 사이클의 존재 여부까지 알려준다. ...