10. 최단경로 알고리즘(벨만포트, 다익스트라)

2021-08-03

2022-01-23

최단 경로 알고리즘

아주 중요한 그래프 문제.
엣지에 가중치가 부여된 상황에서 특정 노드에서 다른 노드로 가는 최적의 경로를 찾는 문제.

특징

노드 s에서 v까지 최단 경로 중 엣지(u, v)가 포함되면, 이 경로에서 s부터 u까지 부분도 역시 최단 경로다.
M(v)를 s에서 v까지 최단 경로라고 길이라고 하면,
M(V) = M(u)+min(u,v) 인 셈이다! (DP식과 비슷하다?)

벨만포드 알고리듬

relax라는 연산을 배워보자. 아주 중요하다!

d[v] : M[v]를 저장하기 위한 배열 (무한대로 초기화)
p[v] : s-v최단 경로에서 v직전에 오는 노드를 저장하기 위한 배열

def relax(u,v):
    if d[v] > d[u] + cost(u,v):
        d[v] = d[u] + cost(u,v)
        p[v] = u

모든 노드 v에 대해 d[v]가 최단경로(M[v])를 저장할 때까지 relax를 반복!
만약 d[u] = M[u]일때, 엣지 (u, v)에 대해 relax 함수를 호출하면, d[v] = M[v]가 된다!

이런 식으로 하나하나 relax 해가면 어떤 특정 노드까지 최단 경로를 찾을 수 있다!

벨만 포드 알고리즘 psuedo code

def Bellamn-Ford(G = (V, E)):
    d = [inf]*n, d[s]=0
    for i in range(1,n):
        for each edge e = (u, v): #매번 엣지마다
            relax(u,v)
    return d

(n-1) * all edges…
벨만포드는 O(nm)=O(n^3)의 복잡도를 가진다.

다익스트라 알고리듬

다익스트라 알고리즘에서는 현재까지 d[v]값 중 최소 값을 고르면 d[v] = M(v)이다.(greedy)
d[v]가 결정되고 나서 인접한 이웃노드들에게 relax하면 그들의 d값도 다 갱신될 수 있다!

모든 d[v] 중 최소 값이 매번 필요하므로, minHeap, 즉 최소값이 최상단노드가 되는 힙이 필요하다!
minHeap에는 deleteMin과 decreaseKey 연산이 필요하다.

deleteMin: 말 그대로 힙의 최상단 노드를 제거하고 다시 힙정렬하는 연산
decreaseKey : 힙의 어떤 노드의 키값을 변경(인하)하고 힙정렬하는 연산

다익스트라 알고리즘은

각 노드까지 최단 경로 중 가장 작은 값을 제거
가장 작은 값의 노드 이웃노드를 상대로 벨만 포트 식 진행
이웃 노드들의 값이 달라지면 반영.(물론 더 작아진 경우만 반영)
모든 노드가 힙에서 사라질 때까지 다시 1번부터 반복

psuedo code로 구현해보자.

def Dijkstra(G):
    n, m = numbers of nodes and edges of G
    s = source node, simply 0
    d = [0, inf, inf, ... inf]
    parent = [0, None, None, ... , None]
    H = make_heap(nodes v of G with key d[v])
    while len(H): #heap에 아무것도 없을때까지.
        u = H.deleteMin() #heap의 최상위 노드, 즉 최소값 제거
        for each v adjacent to u : #최소값 갖는 노드와 인접한 노드 v
            if(u, v) is an edge of G:
                if d[u]+cost(u,v)< d[v] : #벨만포트 식!
                    d[v] = d[u] + cost(u, v)
                    parent[v] = u
                    H.decreaseKey(v, d[v]) # 값을 수정시키고 힙의 위치 알맞게 조절
    return dist, parent

다익스트라 알고리즘의 수행시간?
make_heap : n* insert
while loop : n * deleteMin
for loop : m * decreaseKey
=> 어떤 힙을 쓰느냐에 따라 다르다!

minHeap = O((n+m)log n)!
FibonacciHeap = O(n log n + m)

All to All shortest Path problem

지금까지는 source to All 최단 경로를 구하는 알고리즘이었다.

이젠 모든 노드쌍에 대해 최단 노드를 구해보자.

for each node s in V: Dijkstra(s) = O(다익스트라 연산 * n)= O(n * m * log n) =O(n^3)
DP 방법. Floyd-Warshell 알고리즘

Floyd Warshell 알고리즘

sp(a, b) = 노드 a, b의 최단 경로이고, d(a,b)는 해당 경로의 최단 경로 비용이라고 할 때,

sp(i,j) = sp(i,k) + sp(k,j) 이므로,
d(i,j) = d(i,k) + d(k,j)가 성립한다! =>DP식!

px(a, b)를 px(a, b) = p(x-1)(a, x)+p(x-1)(x, b)를 만족하는 중간 노드 값 x에 대한 식이라고 하면,
pn(a, b) = p(n-1)(a, n) + p(n-1)(n, b)
즉 dn(a, b) = d(n-1)(a, n) + d(n-1)(n, b) 혹은 d(n-1)(a,b). 이 두 값 중 최솟값이 되겟다.

이 식을 기반으로 n이 0일때, 1일때 dp테이블을 작성해 나아간다.

이를 간단하게 구현하는 과정을 설명하자면

d를 표현하기 위한 2차원 리스트(n*n)를 무한대로 초기화해서 선언
d 초기에는 만약 (i,j)가 엣지가 존재하면 d[i,j]를 해당 엣지 가중치로 할당
for k in range(1,n+1)로 4번을 루프 돌린다.
모든 (i,j)에 대해 d[i][j] = min(d[i][j], d[i][k]+d[k][j])

이 과정을 마치고 나면 (i,j)에 대해 최소 경로를 얻을 수 있다!

mudura

Computer ScienceData Structure