플로이드워셜

최단 거리 알고리즘의 이해

최단 거리 알고리즘에 대해 정리해 본다. 책을 참고했음을 밝힌다. 최단 거리 알고리즘은 말 그대로 시작 지점에서 도착 지점까지 이동하는 경로 중 가장 짧은 경로의 거리를 구하는 알고리즘이다. 장소와 길은 그래프로 나타내기 때문에, 그래프 이론과 밀접한 관련이 있다. 1. 다익스트라 알고리즘 (Dijkstra's algorithm) 가장 스탠다드한 최단 거리 알고리즘이다. 시작 정점을 지정하면 해당 정점에서 출발해서 다른 정점으로 도착할 때의 최단 거리를 알 수 있다. 길찾기 알고리즘을 적용하는 가장 흔한 예는 가중치(weight)가 있는 weighted graph이므로, 나중에 발견된 정점이 최단 거리일 수 있다. 즉, 단순한 BFS로는 최단 거리를 찾지 못하는 경우가 수없이 많다는 것이다. 다르게 말하..