[Algorithm] 다익스트라 (Dijkstra algorithm), 벨만 포드(Bellman ford algorithm)

그래프에서 특정 노드에서 특정 노드까지 가는 최단 거리를 구하는 알고리즘에 대해서 공부해보려 한다.

 

다익스트라 알고리즘과 벨만 포드 알고리즘이 있는데 이 둘의 차이는 그래프의 가중치가 음수를 허용하냐 허용하지 않냐의 차이다.

 

이 둘의 차이점을 기준으로 공부해보려 한다.

 

Dijkstra algorithm

다익스트라 알고리즘은 음의 가중치를 허용하지 않고 양의 가중치만 존재할 때 최단 거리를 구하는 알고리즘이다.

 

최단 거리를 알고있는 노드와 최단 거리를 모르고있는 노드로 나눈다.

 

최단 거리를 모르고 있는 노드의 최단거리를 알아내는 것을 반복하는 알고리즘이다.

A를 선택하고 연결된 노드 B와 C를 비교한다.

 

먼저 가장 짧은 거리인 5만큼 떨어져있는 C의 최단 경로는 5라고 확정할 수 있다.

 

여기서 의문이 생길 수 있다. A-C가 아니라 A-다른 노드 -C와 같이 다른 노드를 경유해서 왔을 때가 최단 경로일수도 있지 않을까?

 

하지만 우리가 C까지 가는 최단 경로를 5라고 확정지은 이유는 A와 연결된 노드들 중 가장 짧은 거리이기 때문이다.

 

또한 다익스트라 알고리즘에서는 음의 가중치를 허용하지 않는다.

 

즉 A와 연결된 다른 노드를 경유한다면 A에서 다른 노드로 가는 순간 A-C로 가는 경로보다 같거나 클 수 밖에 없기 때문이다.

 

이것이 A와 연결된 노드들 중 가장 가까운 노드의 최단거리를 우선적으로 확정하는 이유이다.

 

물론 B는 A에서 바로 가는 것이 최단거리라고 아직은 확정할 수는 없다.

이제 다시 최단 거리를 알고있는 노드들과 연결된 노드들을 확인한다.

 

A-B : 7

A-C-B : 14

A-C-D : 11

 

이제 B의 최단경로는 A-B이고 거리는 7임을 확정할 수 있다.

A-C-D : 11

A-B-E : 14

 

이제 D의 최단 경로를 확정할 수 있다.

A-B-E : 14

A-C-D-E : 19

A-C-D-F : 22

 

이제 E의 최단 경로를 확정할 수 있다.

A-C-D-E-F : 23

A-C-D-F : 22

 

최단 경로는 A-C-D-F이고 최단 거리는 22이다.

 

Bellman ford algorithm

벨만 포드 알고리즘은 음의 가중치를 허용할 때 최단 거리를 구하는 알고리즘이다.

 

다익스트라 알고리즘에서는 최단거리가 정해진 노드와 연결된 가까운 노드의 최단거리를 확정할 수 있었다.

 

그런데 음의 가중치를 허용한다면 다른 노드를 경유해서 더 짧은 거리가 나올 수 있기 때문에 다른 방법을 사용한다.

 

시작 노드와 연결된 노드들의 시작 노드로부터 k개의 에지를 사용하여 갈 수 있는 최단 거리를 구한다.

 

최단 거리를 구한 노드들과 연결된 노드들의 시작 시작 노드로부터 k+1개의 에지를 사용하여 갈 수 있는 최단 거리를 구한다.

 

위 방법을 반복하게 되면 최단거리를 구할 수 있다.

위 그래프의 경우 시작 노드 A에서부터 1개의 에지를 사용하여 갈 수 있는 노드는 B와 C이다.

 

1개의 에지를 사용할 경우 최단 거리는 B는 2, C는 5이다.

 

시작 노드 A에서부터 2개의 에지를 사용하여 갈 수 있는 노드는 C이다. (A-B-C)

 

2개의 에지를 사용할 경우 C의 최단 거리는  5 - 4 = 1이다.

 

이런식으로 목적지에 도착할 때까지 반복하면 된다.