Dijkstra 적용 조건
우선순위 큐를 쓰면 O((V+E)logV) 형태로 관리합니다.
최단 경로 선택 기준
Dijkstra, Bellman-Ford, Floyd-Warshall은 음수 간선과 모든 쌍 거리 요구에서 서로 갈립니다.
Bellman-Ford 적용 범위
V-1번 완화를 반복하므로 큰 그래프에서는 비용이 큽니다.
모든 정점 쌍의 최단 거리가 필요할 때 행렬로 풉니다
O(V^3)라 정점 수가 작을 때 선택합니다.
INF와 시작점 0
완화 후 값이 줄어드는지 로그로 보면 오류를 찾기 쉽습니다.
음수 간선
Dijkstra는 음수 비용에서 확정 순서가 깨질 수 있습니다.
질의 범위
단일 시작점인지 모든 쌍인지가 알고리즘 선택을 바꿉니다.
그래프 크기
V와 E의 크기 차이가 우선순위 큐와 행렬 선택을 가릅니다.