MIT - Introduction to Algorithms - Lecture 15. Single-Source Shortest Paths Problem 단일 시작 최단 거리 문제 Review

MIT - Introduction to Algorithms 

- Lecture 15. Single-Source Shortest Paths Problem 

단일 시작 최단 거리 문제 Review

Copyright to MIT & Srini Devadas & Erik Demaine
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/
code, data, note pdf  : https://courses.csail.mit.edu/6.006/fall11/notes.shtml
한글 번역과 슬라이드를 보고싶은 분은 Edwith - 파이썬을 이용한 알고리즘의 이해 항목 강의를 참조하세요.
URL : https://www.edwith.org/introalgorithm/

 수학적인 관점과의 차이는 이번은 간선에 가중치가 있다는 점
물론 가중치는 실수, 유리수, 음수일 수도 있다.
최적해와 최적 부분 구조 조건이라 불리는 Optimal SubStructure에 대한 성질을 알아볼 것
효율적인 복잡도를 얻기 위해 점근적인 복잡도를 가지는 알고리즘을 원함
이를 얻기 위해 사용하는 도구가 최적 부분 구조 Optimal SubStructure

동기 Motivation
가장 빠르게 Caltech에서 MIT로 물품을 가져오고 싶다.
G(V,E,W) #V:Vertexes, E:Edges, W:Weights
W:E->R # Edges에 실수의 가중치를 준다

다음 시간에 걸쳐 2개 알고리즘을 알아볼 것 :
1. Dijkstra(병행 프로그래밍에서 비슷한 일로 튜링상을 받음)
음이 아닌 edge 가중치 weight를 가정했을 때 $O(V log_2(V)+E)$ : 선형 시간
일반적 단순 그래프에서 $E=O(V^2)$
완전 그래프 : 모든 정점들 사이에 간선이 존재하는 그래프 $E=O(V^2)$
2. Bellman Ford : $O(VE) = O(V^3) vs O(Vlog_V)$
왠만하면 Dijkstra를 사용하고 막히면 Bellman Ford 사용

최종적으로는 음의 가중치를 찾는 순환을 찾는 것이 목표
그러나 음의 가중치를 가지는 간선의 어려운 점은 짧은 경로를 찾으려는 최단 경로 알고리즘의 허를 찔리게 되기 때문
가령 음의 가중치를 가지는 Edge를 가는 것 만으로도 전체 가중치를 줄일 수 있으므로 오류가 생김
때문에 더 많은 연산과 알고리즘을 복잡하게 만들게함

find p with minimum weights

위에서 말한 2가지 알고리즘 Dijkstra, Bellman Ford는 가중치에 대한 함수로 이뤄지지 않았다.
최단 경로 알고리즘에서 가중치의 범위는 지수적일 수도 있고 가중치는 오직 $E^2$개의 다른 값만을 가질 수 있지만 W는 복잡도에 영향을 미치지 않는다.
DFS, BFS가 최단 경로 문제에 적용이 불가능한지 다음 시간에 설명 : 가중치의 동적 범위 때문

최단 경로 문제가 왜 어려운가
경로의 수가 지수적으로 존재하기 때문

Shortest path weight from u to v를 $\delta$ delta 표기 가능
ex) MIT -> Tokyo 육로로 가는 최단 거리는 무한대를 가질 것임 : 태평양이 존재하기 때문
시작점으로부터의 도착점까지의 최단 경로 시작은 0이 아닌 무한대에서 줄여나가는 것 (어떠한 경로도 찾지 못했기 때문)

NIL = nothing

음이 아닌 가중치를 갖는 단순 그래프 예제
$\delta(S,C) = 6$ #S->A->C
$\delta(S,C) = 5$ #S->B->C 가중치가 더 적으므로 이 path 채택

왜 Negative-Weight Edges가 필요할까
학생 예) 운전에서의 거리가 음수는 의미가 없지만 돈을 받고 운전을 하는 경우와 돈을 지불하고 운전을 하는 경우
고속도로의 교통량을 조절하기 위한 통행세의 경우 etc

자세한 내용에 대해서는 벨만 포드에서 배울 것

Negative weight Cycles가 있으면 사이클을 도는 것만으로도 weight가 낮아지므로 최단 거리의 본래의 취지와 다른 방식으로 길을 찾게 되고 무한히 반복됨
4p Figure 2. BCD Cycle 참조

종료 조건 terminate condition이 제대로 설정되어 있지 않으면 무한 루프를 도는 알고리즘적 버그가 됨
다른 양의 weight에서는 잘 작동 : $\delta(S,S)=0, \delta(S,A)=2$
따라서 음의 사이클을 잘 처리하는 알고리즘을 구현해야함(음의 가중치를 가지는 간선 자체는 문제가 되지 않음)
그래야만 음의 사이클이 최단 거리를 정의할 수 없게 만드는 문제를 해결 가능

벨만 포드 알고리즘이 음의 사이클을 감지 후 합리적 시간 안에 종료할 수 있어야함 O(VE)
다익스트라는 전제 조건 자체가 non-negative edge weight이므로 더 간단

General Structure of S.P Algorithms
Relax edge(u,v)에서 $\Pi[v]=NIL==d[v]=\infty$
ex) Figure 1.에서 $\delta(S,C)=6, \Pi[C]=A$를 $\delta(S,C)=5, \Pi[C]=D$로 수정하는 과정
음의 사이클이 없는 경우 종료는 어떤 간선도 완화 Relaxation, 갱신 Improvement이 불가능할 때로 종료 조건이 명확하다.
=> 느리지만 잘 작동(물론 나쁘게 작동하는 예가 뒤에 나옴), 그러나 구현하고 싶지 않은 별루인 알고리즘

그래프에 지수적으로 많은 Edges가 존재할 경우 알고리즘이 문제가 되는 예시
가변적인 가중치의 범위에 상관없이 작동
가중치는 $2^{{n \over 2}}$로 변화된다고 가정
n=100일 수도 혹은 $2^{50}$이 될 수도 있다. &lt 64 bits
Edges : $(V_0, V_1)=4, (V_1, V_2)=4, (V_0, V_2)=4, (V_2, V_3)=2, (V_3, V_4)=2, (V_2, V_4)=2, (V_4, V_5)=1, (V_5, V_6)=1, (V_4, V_6)=1 \cdots$

어떤 Edge를 선택하냐에 따라 Vertex의 weight가 달라진다.
때문에 다음 수업은 어떻게 edge 간선을 올바르게 선택할 수 있는지 배울 것

간선이 아닌 경로 path에 대해 Triangle Inequality 조건을 만족
이 알고리즘은 선형 시간 알고리즘으로 바꿈