그래프 - 다익스트라 알고리즘

다익스트라는 최소 알고리즘을 구하는 알고리즘이다.

다익스트라 알고리즘을 보기전에, 다익스트라의 알고리즘의 원형이라고 볼 수 있는 BFS를 알아보겠다.

이 글에서는 BFS의 개념에 대해서 다루지 않는다.

 

1. BFS - Shortest Path.

BFS는 대표적으로 모든 간선의 길이가 1일 때, 가장 짧은 거리를 구할 수 있는 알고리즘이다.

만약 간선이 1이 아니라면 어떨까?

 

위와 같은 그래프에서 BFS를 적용하려면 아래와 같이 모든 간선을 1로 바꾸는 편법을 써서 BFS로 풀 수 있다.

실제로 이렇게 간선을 추가하는것은 너무 비효율적인 일이니, 이런 그래프 모양을 생각하고 조금 효율적으로 바꿔보겠다.

 

d'(node) = 시작노드부터 - node까지 "임시" shortest path // bfs처럼 확장하되, 아직 shrotest path로 확정된 거리는 아니다.

d(node) = 시작노드부터 - node 까지 확정 shortest path  // shortest path로 확정된 거리다.

라 하자.

 

확정거리 d를 구하기 위해서는 임시 d' 중에 가장 짧은 거리가 확정거리이다.

 

다시말해, 위 사진에서 중간에 껴넣은 노드를 포함해서 BFS를 수행한다고 가정할 때, 가장 먼저 원했던 노드에 도착하는 것은 사이의 노드 개수가 적은것이 된다. 즉, d'는 시작노드부터 타겟노드의 사이의 노드의 개수를 알려주고 그 노드의 개수가 적은게 BFS상으로 가장 빠르게 도달하는 경로이므로 확정 shortest path가 된다는 아이디어이다.

 

 

위 아이디어로 bfs를 응용하여 시작 노드를 기준으로 가장 짧은 거리를 모두 구해보겠다.

 

1. 빨간색 노드를 시작점으로 하고, bfs처럼 확장하면서 d' 를 업데이트 해준다. 빨강은 확정거리 0으로 정해졌다.

 

2. 확정거리 d가 정해지지 않은 노드 중 가장 짧은 d'를 구한다. 

이 d'는 확정거리가 된다.

그리고 그 노드가 확장할 수 있는 노드의 d'를 업데이트해준다.

다음 임시거리 d'는 = 현재의 확정거리 + len(현재 노드 -> 다음노드)의 길이이다.

 

아래의 사진에서 분홍색은 가장 짧은 d'로 선택되었고, 다음 연분홍 노드를 기준으로 임시거리 d' 를 업데이트 해주었다.

3. 또 다시 2번으로 돌아간다.

확정거리로 선택되지 않은 노드중에서 임시거리가 가장 짧은걸 선택한다.

그리고 그걸 확정거리로 바꾼 뒤, 임시거리를 업데이트 한다..

 

아래의 예시를 보면 분홍색 노드가 d'= 3으로 새로운 확정거리로 뽑혔다고 가정하자.

새로운 임시노드인 연분홍 노드를 업데이트 시켜줘야하는데, 기존에 d'=6 으로 이미 업데이트 되어있다.

짧은 길이를 업데이트 해줘야 하므로 d'가 더 적은 4로 업데이트해준다.

 

 

4. 다시 2번 과정을 반복한다

확정거리로 선택되지 않은 노드중에서 임시거리가 가장 짧은걸 선택한다.

그리고 그걸 확정거리로 바꾼 뒤, 임시거리를 업데이트 한다.

나머지 d'중에 가장 짧은것은 d'=4가 되므로 마지막을 업데이트하고 끝낸다.

 

2. 다익스트라 알고리즘 using Heap

BFS를 응용한 위의 알고리즘이 사실 다익스트라 알고리즘의 아이디어와 같다.

실제 구현하는 부분에서 최소 d'를 찾는 부분이 많이 까다로울 것이다.

 

위의 d' 의 최소값을 찾는 부분을 힙으로 교체하면 조금 더 효율적이고 쉬운 구현이 가능하다.

 

1. PQ에 시작노드를 넣는다.

2. PQ가 빌때까지 반복한다.

2-1. PQ에서 임시거리가 가장 적은것을 뽑는다.

2-2. 확정거리로 만들어준다.

2-3. 그리고 다음 임시거리를 업데이트해준다.

 

이 코드를 실제 코드로 보면 아래와 같다

많이 간추렸지만 아이디어는 같다.

 

1. 최적화 아이디어 - 1

 

11번째 if문에서 dist_[there.no] > there.length + dist[here.no] 이 부분 같은경우는 절대로 dist[here.no] 전에 dist_[there.no]를 업데이트 할일이 없으므로 

dist_라는 배열 없애고 dist라는 배열 하나로 만들 수 있다.

 

그리고 최소 거리를 판단한 이후 부터는 임시거리가 아니라 자동적으로 최소거리가 변경 되고, 한번 최소거리가 결정되면 무조건 그건 최소거리이므로, dist_ 같은 임시배열은 의미상으로 필요가 없다. (물론 초기 최소거리를 Inf값으로 설정을 해야한다!)

 

여기까지 줄였으면 시간복잡도가 E log E 가 나온다. 

 

하나의 정점이 큐에 들어갈 때마다, 연결 되어있는 모든 정점을 검사한다.

검사할 때 마다 힙에 들어가거나 혹은 최소 연결 조건이 되지 않으면 들어가지 않는다.

 

힙에 들어가는걸 검사하는 최대 시간은 E이고, 모두 힙에 들어간다면, 힙에 들어갈 수 있는 최대의 개수는 E개 라는것을 알 수 있다.

힙에 들어가는 시간은 log( 힙의 최대크기 )의 시간이 걸리므로, 최대 O( E Log E ) 시간이 걸린다.

 

다익스트라에서 음수 사이클을 허용할 수 없는 경우

문제를 풀다보면 다익스트라를 풀지 못하는 경우가 꽤 많다.

대부분이 음수 사이클인데, 음수 사이클이 존재하면 무한 루프를 돌기 때문이다.

 

이는 다익스트라의 거리 확장 특성 때문인데, 아래와 같은 예시를 보겠다.

위의 그래프에서는 A부터 시작해서 확장거리를 B로 확장해 나간다.

1. A라는 노드에서 -> B의 임시거리를  20으로 업데이트

2. B로 확정. B라는 노드에서 -> C라는 노드를 50으로 업데이트.

3. C도 확정. C라는 노드에서 A라는 노드를 -70으로 업데이트.

4. A변경 A는 -50이라는 값으로 A에 도달가능함. 

5. B변경 A는 -30이라는 값으로 B에 도달 가능함.

6. C변경 A는 0이라는 값으로 C에 도달 가능함.

7. C는 임시거리로 A에게 -100을 주입.

8. A는 임시거리로 B에게 -80을 주입.

9. B는 임시거리로 C에게-60을 주입.

10. C는 임시거리로 A에게 -160을 주입.

11. ...무한루프..

 

이렇게 무한루프가 일어난다.

사실 문제는

1. 한번 방문했던 정점을 제외하는 방식을 택하면 잘 작동해 보이지만, 아래와 같은 경우 음수 가중치가 있는 그래프에서 정확한 값을 구할 수 없을 수 있다. 음수 가중치를 고려한 경로가 더 빠를 수 있다는 점이다. 아래의 경우 답은 1 -> 2 -> 3인데 1->3으로 결론내 버린다.

https://blog.encrypted.gg/918

2. 한번 방문했던 정점을 제외하는 방식이 아니라면, 음수 사이클에서 무한루프가 발생한다.