Dijkstra's Algorithm

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 관계를 가진다.

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

from http://handong201.tistory.com/86 by ccl(A) rewrite - 2021-12-10 17:26:51