Dijkstra's Algorithm

 

Shortest Path Problem

 

Weight graph는 Node 와 Edge 그리고 weight가 있는 그래프를 의미한다.

(V, E, W) Node 간의 연결성과 특징을 보여주는 것이 W이다.

Path = sequence of edge 

length of path 는 number of edge 가 된다. 

Q) What is shortest path?

Boston 에서 LA로 가는 가장 짧은 길은 어떤 조합이 될까..?

 

 

 

Positive weight를 가지고 있음을 가정한다.

a에서 z 로 가는 Shortest Path를 찾는다.

: 해당 노드의 주변만을 확인하면서 시작 노드로 부터 어느 길이 가장 짧은 길이 되는지를 확인한다.

모든 과정을 할 필요없이 이웃으로 부터 Path의 길이가 얼마였는지만 기억하고 있다면 최단 거리를 찾을 수 있다.

 

 

Start Vertex와 Ending Vertex는 알려주고 시작해야 한다.

Weigth 는 항상 Positive weight가 있음을 가정해야 한다.

(음수가 있고 Cycle이 존재하면 최단 거리를 정의할 수 없다.)

L: V -> R (Vertex 에 대한 내용을 가지고 있는 함수)

L(v)가 표현하고자 하는 것은 a에서 출발해서 v까지 가는데 shortest Path를 의미한다.

처음 L(v)는 얼마나 걸리는 지 알지 못한다. 연결이 안되었을 가능성도 존재한다.

S 는 계산이 끝난 것들을 모아가는 Vertex

루프가 시작하고

S에 z가 속하지 않을 때까지 반복을 하고 S에 속하지 않는 V 마다 L(u) + w(u,v) < L(v) 라면 

L(v) 에 L(u) + w(u,v) 를 할당해서 해당 V 노드로 가는 최단 거리에 대한 정보를 최신화해준다.

 

S의 영역을 한 칸씩 키우고 싶은 것. 

S는 이미 통과한 Vertex로 이루어져 있고 S에 속하지 않은 그 다음 Vertex 중 최단 거리를 만족하는

L(u) + w(u,v) < L(v) 를 만족한다면 최단 거리에 대한 값을 새로 최신화 해준다.

여기서 L(v) 는 지금까지 알려진 시작 노드 a에서 출발해서 v 노드까지 도착하기 위해 걸리는 path가 된다.

 

Mathematical Induction Proof

S를 통해서 찾아진 경로 중 최단 거리만을 선택한다는 것이 Inductive Hypotheses

 

가정에 따르면 S에 속하지 않은 V' 을 통해서 U 로 가는 최단 거리 방법이 존재해야 한다.

하지만 V'은 항상 S 안에 속한 것이 되는 모순이 발생한다. 

왜냐하면 현재 가장 짧은 길로 가는 방법이 존재하는 경로는 항상 S를 통할 수 밖에 없음이 전제가 되기 때문이다.

N x N 만큼의 Time이 걸린다. 하나의 Vertex 당 모든 Vertex를 탐색하므로

 

 

Find a circuit을 하는 것은 다른 문제이다. (TSP 문제)

Hemilton Circuit을 얘기할 때 언급한 적 있음

해당 도시를 한 번 씩만 방문하고 싶은데 그 중 가장 짧은 길로 다닐 수 있는 방법에 대한 알고리즘

모든 경로를 탐색하는 것보다 더 좋은 알고리즘이 존재하지 않는다.

모든 경로를 다 보지 않고 탐색할 수 있는 방법에 대한 알고리즘은 존재하지 않는다.

Arbitrary graph 즉, 일반적인 Solution은 없지만 Efficient 한 Common Case 에 대한 Solution은 존재한다.

Common 이라는 것은 자주 나오고, Popular 한 것들, 일정 조건에 대해 만족하는 Graph에 대해서

efficient 하게 돌아가는 알고리즘이 존재한다. 

 

Sequence를 주면 해당 Path의 Weight를 찾을 수는 잇다.

Weight를 구하는 것은 하기 쉽다. 현재 시점에서 Evaluation을 할 수 있다.

Random 한 Sequence를 주고 어떤 값이 가장 좋은지를 알 수 있다.

Trial Error를 하면서 발생한 Information을 잘 Search를 한다.

그래서 해당 Sequence와 비슷한 Sequence를 만들어보자라는 관점으로 Problem Solving을 진행한다.

해당 Sequence에 대한 규칙을 살짝 살짝식 바꿔주면서 찾아나간다.

 

 

수학적 증명은 수학적 사실의 Subset 관계를 가진다.

증명은 안됐지만 사실이다.