[그래프 탐색] 최단거리 알고리즘 종류 // 수정 예정

일단 여기서 말하는 "최단거리"란 노드의 수가 아니라 가중치가 1이 아닌 그래프에서 말하는 것이다.

 

1. 다익스트라 알고리즘 (Dijkstra's Algorithm)

- 가장 유명한 알고리즘으로, 단일 정점의 최단경로를 구할 수 있다.

 

2. 벨만 포드 알고리즘(Bellman-Ford Algorithm)

- 음의 가중치를 가진 경로에서도 최단거리를 구할 수 있다. 경로 추적이 가능하다.

 

3. 플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)

- 단일정점이 아닌 모든 정점 사이의 최단거리를 구할 수 있다.

 

4. SPFA(Shortest Path Faster Algorithm)

- STL없이 간단하게 구현 가능하며, 평균적으로 빠른 속도를 가진다.

 

출처 : https://semaph.tistory.com/9

최단거리 알고리즘 종류

알아보고 내용 수정하자!