최단경로(Shortest Path)

📢  최단경로

• 최단경로 문제(Shortest Path Problem)
  
  👉가중그래프와 두 개의 정점 u와 v가 주어졌을 때, u와 v사이의 무게의 합이 최소인 경로를 구하는 문제
  
  
• 최단경로길이 : 간선들의 무게 합
• 응용분야
  
  👉 인터넷 패킷 라우팅, 항공편 예약, 자동차 네비게이션 등등

 

📢  최단경로 속성

• 속성 1
  
  👉 최단경로 부분경로(Subpath)역시 최단경로이다.
  
  
• 속성 2
  
  👉 출발정점으로부터 다른 모든 정점에 이르는 최단경로들의 트리가 존재한다.
  = 단일점 최단경로(Single-Source Shortest Paths)
• 최단경로는 최소신장트리와 달리
  
  👉 무방향뿐만 아니라 방향그래프에도 정의된다.
  👉 그래프에 음의 무게를 가진 싸이클이 있거나, 무방향그래프에 음의 무게를 가진 간선이 있으면 부정한다.
  👉 최단경로트리(Shortest Path Tree)는 루트트리
  
  
• 가중 방향그래프에 음의 무게를 가진 싸이클이 존재
  
  👉 최단경로는 존재하지 X
  
  
• 가중 무방향그래프에 음의 무게를 가진 간선이 존재
  
  👉 최단경로는 존재하지 않는다.
  
  
• 최단경로 알고리즘

그래프	알고리즘	시간
음이 없는 무게를 가진 간선이 없는 그래프	Dijkstra(다익스트라)	O(Mlog(N)) or O(N^2)
음의 무게를 가진 간선이 있는 방향그래프	Bellman-Ford(벨만-포드)(BFS에 속함)	O(NM)
비가중그래프	BFS	O(N + M)
DAG ( 방향 비싸이클 그래프)	Topological Ordering(위상정렬)	O(N + M)

 

📢  Dijkstra 알고리즘

• 정점 s로부터 정점 v의 거리 : s와 v사이의 최단경로의 길이
• Dijkstra 알고리즘은 출발정점 s로부터 다른 모든 정점까지의 거리를 계산한다.
• 전제
  
  👉 그래프가 연결되있다.
  👉 간선들은 무방향이다.
  👉 간선의 무게는 음수가 아니다.
  
  
• 정점 s로부터 시작하여 정점들을 차례로 배낭에 넣다가 결국엔 모든 정점을 배낭에 넣는다.
• 각 정점 v에 거리 라벨 d(v)를 저장하여 배낭과 인접 정점들을 구성하는 부그래프에서 s로부터 v까지의 거리를 표현
• 반복의 각 회전에선
  
  👉 배낭 밖의 정점 가운데 거리 라벨 d가 최소인 정점 u를 배낭에 넣는다.
  👉 u에 인접한 정점들의 라벨을 갱신한다.
• 결과적으로, 최소신장트리의 Prim-Jarnik알고리즘과 매우 흡사한 것을 느낄 수 있다.

Alg DijkstraShortestPaths(G,s)
	input a simple undirected weighted graph G with nonnegative edge weights, vertex s of G
    ouput lable d(u), for each vertex u of G, s.t. d(u) is the distance from s to u in G

for each ∈ G.vertexs()	
    d(v) <- ∞					// 모든 정점의 거리는 0

d(s) <- 0						// 시작 정점 s의 거리는 0
Q <- a priority queue containing all the vertexs of G using d labels as keys

while(!(Q.isEmpty())
    u <- Q.removeMin()			// 힙으로 구현한, Q 에서, 최소힙의 루트키를 반환해서, 최소 값 정점 u를 반환
    for each e ∈ G.incidentEdges(u)	// u에 부착된 간선들 전부에 대해
        z <- G.opposite(u,e)			// z는 정점 u와 부착된 간선을 통한 반대편 정점
        if(z ∈ Q.elements())			// 그 정점 z가 아직 Q에 존재하는, 즉, 아직 배낭에 들어가지 못한 정점이면
            if(d(u) + w(u,z) < d(z))		// 간선완화진행 ( 기존의 정점 z의 distance보다 > 앞선 u정점과 이어진 간선 (u,z)의 distance의 합이 더 작으면 
                d(z) <- d(u) + w(u,z)		// d(z) 업데이트
                Q.replaceKey(z,d(z))		// 그리고, z정점의 가중치가 업데이트 됬으면, 전체, Q 구조 업데이트

 

•  추가설명
  
  👉 배낭(Sack) : 가상이므로, 구현하지 않음 !!
  👉 우선순위 큐가, 배낭 밖의 정점들을 보관한다. = ( 키(distance)-원소(vertex) )
  👉 각 정점 v에 두 개의 라벨을 저장 = ( 거리( distance ) : d(v) , 부모 정점( parent ) : p(v) )
  
  

 

📢  간선완화

• 간선 e = (u,z)에 대해 고려한다.
  
  👉 u는 가장 최근에 배낭에 들어간 정점
  👉 z는 배낭 밖에 존재하는 정점
• 간선 e의 완화(relaxation)를 통해 거리 d(z)를 갱신한다. 즉,
  
  👉 d(z) <- min( d(z) , d(u) + w(u,z) )

간선 완화(edge relaxation) 예시

 

Dijkstra 알고리즘 예시 ( A부터 시작해서, 배낭에 추가되는 것, 동시에 주변 정점에 써있는 distance의 변화를 유의 )

 

•  알고리즘 분석
  
  👉 우선순위 큐의 구현에, 두 가지 선택 가능
  
  1. 힙 구현
  2. 무순리스트 구현
  
  
• 힙에 기초한 우선순위 큐를 사용할 경우
  
  각 정점은 우선순위 에 한번 삽입, 한번 삭제되며, 각각의 삽입과 삭제에 = O(log(N)) 시간 소요
  우선순위 큐 내의 정점 z의 키는 최대 deg(z)번 갱신되며 각각의 키 갱신에 = O(log(N)) 시간 소요
  
  👉 그래프 G가 인접리스트 구조로 표현된 경우, Dijkstra 알고리즘 = O((N+M)log(N)) 시간에 수행
  👉 그래프가 연결되어 있으므로, 실행시간 = O(Mlong(N)) 표현 가능
  👉 그래프가 단순하다고 전제하므로 = (최악의 경우) O(N^2log(N))
  
  
• 무순리스트에 기초한 우선순위 큐를 사용할 경우
  
  각 정점은 우선순위 큐에 한번 삽입, 한번 삭제되며, 삽입과 삭제에 = 삽입( O(1) ), 삭제( O(N) ) 시간 소요
  우선순위 큐 내의 정점 z의 키는 최대 deg(z)번 갱신되며 각각의 키 갱신에 O(1) 시간 소요
  
  👉 그래프가 인접리스트 구조로 표현된 경우, Dijkstra 알고리즘 = O(N^2 + M) 시간에 수행
  👉 그래프가 단순하다고 전제하므로 = O(N^2)로 단순화 가능
  
  
• 결과적으로, 두 가지 우선순위 큐 구현 비교 ( 힙 vs 무순리스트 )
  
  👉 힙으로 구현하면 = O(Mlog(N)) 시간 소요
  👉 무순리스트로 구현하면 = O(N^2) 시간 소요
  
  👉 두 구현 모두 : 코딩하기 쉽고, 상수적 요소로 보면 비슷하다.
  👉 (최악의 경우만을) 생각하면, 다음과 같은 선택지가 있다.
  
  1. 희소그래프( 즉, M < (N^2)/log(N) )에 대해서는 힙 구현이 유리
  2. 밀집그래프( 즉, M > (N^2)/log(N) )에 대해서는 구현이 유리
  
  

 

📢  Bellman-Ford 알고리즘

• 음의 무게를 가진 간선이 있더라도 작동한다.
• 방향간선으로 전제한다 = If ) 그렇지 않으면, 음의 무게를 가진 싸이클이 있게 되기 때문이다.
• i - 번째 회전 시에 i 개의 간선을 사용하는 최단경로를 찾는다.
• 실행시간 : O(NM)
• BFS에 기초한다. = 음의 무게를 가지는 싸이클이 있는 경우, 이를 발견 가능하다.
• 인접정보를 사용하지 않으므로, 간선리스트 구조 그래프에서 수행 가능하다.

Alg Bellman-FordShortestPaths(G,s)
	input a weighted digraph G with n vertexs, and a vertex s of G
    output label d(u), for each vertex u of G, s.t. d(u) is the distance from s to u in G

// 그래프 내의 모든 정점 distance = ∞
for each v ∈ G.vertexs()
    d(v) <- ∞
    
d(s) <- 0						// 시작 정점 s에 distance = 0
for i <- 1 to n - 1		
    for each e ∈ G.edges()			// 그래프 내의 모든 간선으로 부터
        // 간선완화
        u <- G.Origin(e)			// u는 간선 e에 저장된 origin(시작) 정점 
        z <- G.opposite(u,e)			// z는 정점 u와 간선 e로 부터 이어지는 반대편 정점
        d(z) <- min(d(z),d(u) + w(u,z))	// 현재 정점 z의 distance > u정점까지 거쳐 + u와 z정점으로 이어지는 간선 e의 거리의 합 중에 작은 것을 z의 거리로 업데이트

Bellman-Ford 알고리즘 예시 ( BFS 특징 : 한 칸식 늘려가면서 업데이트 하는 느낌 유의 )

 

📢  모든 쌍 최단경로

• 모든 쌍 최단경로(all-pair shortest paths) 문제 : 가중 방향그래프 G의 모든 정점쌍 간의 거리를 찾는 문제
• 그래프에 음의 무게를 가진 간선이 없다면, Dijkstra 알고리즘 N번 호출할 수도 있다. = O(NMlog(N))
• 그래프에 음의 무게를 가진 간선이 있다면, Bellman-Ford 알고리즘 N번 호출할 수도 있다 = O((N^2)M)
• 대안
  
  👉 동적프로그래밍(Dynamic Programming)을 사용 = O(N^3) 시간에 수행 가능하다.
  ( Floyed-Warshall 알고리즘과 유사한 방식으로 수행한다. )
  
  

Alg allPairsShortestPaths(G)
	input a simple weighted digraph G without negative-weight cycle	// 음의 가중치 싸이클 그래프
    output a numbering V1,V2,....,Vn of the vertexs of G and a matrix D 
    (s.t D[i,j] = distance of Vi,Vj in G

Let V1,V2,.....,Vn be an arbitrary numbering of the vertexs of G

for i <-1 to n
    for j <- 1 to n
        if(i == j)
            D[i,j] <- 0			// 자기 자신 distacne = 0
        elseif((Vi,Vj) ∈ G.edges())
            D[i,j] <- w(Vi,Vj)
        else
            D[i,j] <- ∞

for k <- 1 to n
    for i <-1 to n
        for j <- 1 to n
            D[i,j] <- min( D[i,j], D[i,k] + D[k,j] )

동적프로그래밍 기법을 이용한 최단경로 수행 예시