최단거리(Shortest Path)를 구하는 알고리즘은 내비게이션 등 현실에서도 많이 활용되고 있습니다. 이런 최단 거리를 구하는 알고리즘 3개를 알아보겠습니다.
7-1. 플로이드-와샬 알고리즘 (Floyd-Warshall Algorithm)
플로이드-와샬 알고리즘은 Many-to-Many의 최단 거리를 구하는 알고리즘입니다.
인접행렬이 있을 때, 유용하게 사용할 수 있습니다.
7-2. 다익스트라 알고리즘 (Dijkstra Algorithm)
다익스트라 알고리즘은 One-to-Many의 최단 거리를 구하는 알고리즘입니다.
다익스트라 알고리즘은 총 2가지 버전이 있습니다.
- Naive Version
- Priority Queue (Heap) Version
7-3. 벨만-포드 알고리즘 (Bellman-Ford Algorithm)
벨만-포드는 One-to-Many이며 최단거리 중 음의 cycle이 있는지 점검하는 알고리즘입니다.