개발 공부 - [그래프 알고리즘] 순회 - 최단경로(shortest path problem) - 2

Bellman-Ford 알고리즘

: 이어서 수업 

* 릴랙스 하는 순서에 따라서 결과가 달라질 수 있음

: 따라서 진행 되는 결과가 변경 될 수 있긴 함

* 얘는 시간 복잡도 측면에서는 좋은 알고리즘이 아님

Dijkstra의 알고리즘

: 네트워크에서 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다. 최단 경로는 경로의 길이순으로 정해진다. 

Dijkstra의 알고리즘에서는 시작 정점에서 집합 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단 거리를 기록하는 배열이 반드시 있어야 한다.

* 한 번 노드를 선택한 게 있으면 두번 선택 불가 (최단 경로는 중복 불가)

-음수 가중치가 없다고 가정

- s로부터의 최단경로의 길이를 이미 알아낸 노드들의 집합 S를 유지.

맨 처음엔 S={s}.

- Loop invariant : 

u !∈ S 인 각 노드 u에 대해서 d(u)는 이미 S에 속한 노드들만 거쳐서 s로부터 u 까지 가는 최단경로의 길이

- 정리 : d(u) min v!∈S d(v)인 노드 u에 대해서, d(u)는 s에서 u까지의 최단경로의 길이이다.

- 증명은 다른 경로가 존재할 경우에 d(v) >_ d(u) 이므로 모순이라 한다 

(s에서 u까지 다른 최단경로가 존재한다고 했을 때)

d(u)가 최소인 노드 u!∈S를 찾고, S에 u를 추가

S가 변경되었으므로 다른 노드들의 d(v) 값을 갱신

즉, 에지 (u,v)에 대해서 relaxation 하면 루프 불변이 유지됨

요...요약하면

프림이랑 다익스트라는 루프문 내 조금 다른 거 빼고는 똑같다고 볼 수 있어서

사실 Prim 의 알고리즘이랑 동일하다고 보면 된다고 한다 (-.-);;;

어려워서 나무위키 도움을 받음

다익스트라 알고리즘은 다음과 같다. (P[A][B]는 A와 B 사이의 거리라고 가정한다)

1. 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. (정말 무한이 아닌, 무한으로 간주될 수 있는 값을 의미한다.) 보통은 최단거리 저장 배열의 이론상 최대값에 맞게 INF를 정한다. 실무에서는 보통 d의 원소 타입에 대한 최대값으로 설정하는 편.

2. 현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장한다.

3. A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B]와 d[B]의 값을 비교한다. INF와 비교할 경우 무조건 전자가 작다.

4. 만약 d[A] + P[A][B]의 값이 더 작다면, 즉 더 짧은 경로라면, d[B]의 값을 이 값으로 갱신시킨다.

5. A의 모든 이웃 노드 B에 대해 이 작업을 수행한다.

6. A의 상태를 "방문 완료"로 바꾼다. 그러면 이제 더 이상 A는 사용하지 않는다.

7. "미방문" 상태인 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드 하나를 골라서 그 노드를 A에 저장한다.

8. 도착 노드가 "방문 완료" 상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7의 과정을 반복한다.

이 작업을 마친 뒤, 도착 노드에 저장된 값이 바로 A로부터의 최단 거리이다. 만약 이 값이 INF라면, 중간에 길이 끊긴 것임을 의미한다.

7번 단계에서, 거리가 가장 짧은 노드를 고르는 것은 공짜가 아니다. 모든 노드를 순회해야 하므로 시간복잡도에 결정적인 영향을 미치게 되는데, 

이때 제대로 구현된 우선순위 큐를 활용한다면 이 비용을 줄일 수 있다. 

최단거리를 갱신할 때 우선순위 큐에도 <위치, 거리>의 쌍을 넣어주고, 거리가 가장 짧은 노드를 우선순위 큐를 이용해 고르면 된다. 

이진 힙을 이용해 구현한 우선순위 큐의 경우 O(lg N) 출력에 O(lg N)이므로, 모든 노드 순회(O(N))보다 저렴하다. 

우선순위 큐 구현에 피보나치 힙을 사용한 경우 삽입은 평균적으로 O(1), 출력에는 O(lg N)이 걸려 이론적으로 더 나은 시간복잡도를 얻을 수 있다.

단 이진 힙이 훨씬 간단하여 연산에 소요되는 시간이 빠르기 때문에, 엣지의 개수가 적은 경우에는 이진 힙을 사용하는 것이 더 나을 수 있다.

느낀점 : 원리적으로는 이해가 되는데 수도 코드는 Prim 만큼 명확하게 이해가 아직 안 된 것이다. 어쨌든 다익스트라는 아직 미확인 거리는 초기값을 INF(무한) 으로 잡아놓고 하도록 정의하면 되겠지만 고로면 최악의 경우를 고려를 잘 해야겠군...