[알고리즘] 24. 단일 출발지 최단 경로

How to find the shortest route between two points on a map

G = (V, E) : weighted, directed graph
weight function w ;;edge - realvalued weights

sum of the weight on path p

shortest path weight -> u, v까지 길이 있으면 가능한 것중 최소// 무한

Breath first search

BFS(G,s)
	for each vertex u { G.V -{s}
    	u.color = WHITE
        u.d = 무한
        u.파이 = NIL
        
    s.color = GRAY
    s.d = 0
    s.파이 =NIL
    Q = 공집합
    ENQUEUE(Q,s)
    while Q!== 공집합
    	u = DEQUEUE(Q)
        for each v { 인접한 간선
        	v.color = GRAY
            v.d +=1
            v.파이 = u 
            ENQUEUE(Q,v)
       u.color = BLACK

-> 결국 single-source shortest path 를 구할줄알면 , 응용 문제들 풀수 있다

Any subpath of a shortest path is a shortest path

Negative-weight edges

prob: 음의 간선을 포함할수도 있다는 점이다.

무한히 -무한으로 가는경우가 아니면 괜찮고, 아예 음의 간선이 있으면 동작이 안되는 알고리즘도 있고

Cycle

Negative-weight cycle :절대 사용불가
/ positive-weight cycle: 이걸 빼고 생각하면 가능 어쩌피 안들어간다
/ 0weight cycle : 있을 이유가 없다 의미 없음

따라서 shortest path 에서는 사이클이 존재하지 않는다고 가정한다

사이클이 없는 graph의 경우 적어도 v-1개의 간선이 필요하다 따라서 에초에 shortestpath 는 v-1개로 정해두고 구해도 된다

Representing shortest paths

Gㅠ = (Vㅠ, Eㅠ)
Vㅠ = {v (- V !== NIL } 합집합 {s} = {t,y,x,z,s} (왜냐면 s의 파이는 NIL이기 떄문)

Eㅠ = {(vㅠ , v)}

PRINT-PATH(G,s,v)
if v==s
	print s
elseif v.ㅠ == NIL
	print "no path from "s" to "v" exitsts"
else PRINT-PATH(G,s,v.ㅠ)
	print v

Shortest-path 전반적인 방법

INITIALIZE-SINGLE-SOURCE(G,s)
for each vertex v { G.V
	v.d = 무한
    v.ㅠ = NIL
s.d = 0

INITALIZE -> RELAX 여러번 -> shortest path 도출 가능

RELAX(u,v,w)
if v.d > u.d + w(u,v)
	v.d = u.d + w(u,v)
    v.ㅠ = u

벨만포드 알고리즘

Bellman-ford(G,w,s)
INITIALZE-SINGLE-SOURCE(G,s) # O(V)
for i = 1 to |G.V|-1 # (|V|-1) * O(E)
	for G.E의 모든 간선 (u,v)
    	RELAX(u,v,w)
for G.E의 모든 간선 (u,v) # O(E)
	if v.d > u.d + w(u,v)
    	return False
return TRUE

-> O(VE)

INITIALIZE-SINGLE-SOURCE(G,s):
	for 모든 G.V의 모든 노드
    	v.d= 무한
        v.ㅠ = NIL
    s.d = 0

RELAX(u,v,w):
	if v.d > u.d + w(u,v)
    	v.d = u.d +w(u,v)
        v.ㅠ = u

다익스트라 알고리즘

DAIKSTRA(G,w,s)
INITIALZE-SINGLE-SOURCE(G,s) # O(V)
S = 공집합
Q = G.V # O(|V|)
while Q!== 공집합: -> O(V) * O(lgV)
	u = EXTRACT-MIN(Q)
    S = S 합집합 {u}
    for u 주변 모든 노드 
    	RELAX(u,v,w)
        

O((V+E)lgV) = O(ElgV)