[Algorithm] 다익스트라 알고리즘 : 음수 간선이 있으면 안 되는 이유

인트로 [2021.11.15 오타 수정] [2022.08.16 오류 수정] 다익스트라 알고리즘은 가중치 그래프에서 최단 경로를 찾는 알고리즘이다. 단 가중치가 모두 양수라는 조건이 있다. 이러한 이유는 다익스트라 알고리즘은 그리디(Greedy) 기반의 알고리즘으로 최소 거리에 최소 거리를 붙여가면 최종적으로 길을 찾기 때문에 음수 가중치는 고려하지 못한다. 반면 음수 가중치가 포함된 그래프라면 벨만-포드 알고리즘 사용 시 목표 노드까지의 최단 경로를 구할 수 있다. 그렇다면 음수가 포함된 가중치에서 다익스트라 알고리즘을 사용하면 어떤 문제가 발생할까? - - 음수 가중치가 포함된 그래프에서 다익스트라 알고리즘의 문제점을 파악하면 벨만-포드 알고리즘을 더 쉽게 이해할 수 있을 것이다. 다익스트라 문제점 :..