최단 경로를 구하는 문제 유형은 크게 분류하면 아래와 같습니다.

1. 하나의 정점에서 출발하였을 때 하나의 정점까지 최단 경로를 구하는 유형

2. 하나의 정점에서 모든 정점까지의 최단 경로를 구하는 문제

3. 특정 정점으로 가는 모든 최단 경로를 구하는 유형

4. 모든 정점에서 모든 정점으로의 최단 경로를 구하는 유형

벨만-포드 알고리즘

[알고리즘] 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

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

다익스트라 알고리즘과 마찬가지로, 한 노드에서 다른 노드들까지의 최단거리를 구하는 알고리즘 입니다. - 유형 2에 해당

다만, 다익스트라 알고리즘은 아래와 같이 음의 가중치가 존재하는 경우에는 사용할 수 없습니다.

위 그림을 다익스트라 알고리즘을 사용하여 최단경로를 구하게 되면,

• 1번 노드에서 3번 노드를 방문하여 3의 최단 경로를 10으로 갱신
• 1번 노드에서 2번 노드를 방문하여 2의 최단 경로를 20으로 갱신
• 2번 노드에서 3번 노드를 방문하면 5라는 최단 경로를 얻을 수 있지만, 3번 노드를 이미 방문했기 때문에 갱신 불가능

따라서 3의 최단 경로는 5가 맞지만, 다익스트라 알고리즘으로는 10이라는 잘못된 결과를 얻게 됩니다.

이처럼 음의 가중치가 존재하는 경우에 다익스트라 알고리즘을 사용하면 잘못된 결과가 나오는 이유는, 이전에 한번 방문한 노드는 다시 방문하지 않기 때문입니다.

다른 경로에서 음의 가중치가 등장하여 이전에 기록한 비용보다 적어도, 최단 경로 값을 갱신할 수 없기 때문에 잘못된 결과가 나오는 것을 확인할 수 있습니다.