728x90
그래프에서 정점끼리의 최단 경로를 구하는 문제는 여러가지 방법이 있다.
- 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제(single source and single destination shortest path problem)
- 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제(single source shortest path problem)
- 하나의 목적지로가는 모든 최단 경로를 구하는 문제(single destination shortest path problem)
- 마지막으로 모든 최단 경로를 구하는 문제(All pairs shortest path problem).
1번째 시작과 목적지가 두개 정확히 지정이 되어있는 경우 --> A* 알고리즘. (http://www.gisdeveloper.co.kr/?p=3897)
다익스트라는 2번째 single source shortest path problem이다.
플로이드-워셜 알고리즘은 이 중에서 마지막, 모든 최단 경로를 구하는 방법이다.
또한 다익스트라 알고리즘은 음의 가중치를 가진 간선은 못쓴다는 제약이 있다. 하지만 플로이드-워셜에선 사용이 가능하다.
어떤 문제에서 어떤 쿼리가 필요한지 파악하고 빠르게 정확한 알고리즘을 선택하는것도 실력이다.
-코테에서 플로이드 와샬 문제를 다익스트라로 풀고 틀려버린 후 적는 두 알고리즘의 차이점