17. 최단 경로 알고리즘

가중 그래프와 두 개의 정점 $u, v$가 주어졌을 때, $u$에서 $v$ 사이의 가중치 합이 최소인 경로를 구하는 문제를 최단 경로 문제라고 한다.
인터넷 패킷 라우팅, 항공편 예약, 길 안내 서비스 등에서 응용된다.

최단 경로의 속성

1. 최단 경로의 부분경로 역시 최단 경로이다.
2. 출발 정점으로부터 다른 모든 정점들에 이르는 최단 경로들의 트리가 존재한다.

최소 신장 트리와의 비교

최단 경로는 최소 신장 트리와 달리, 무방향 뿐 아닌 방향 그래프에서도 정의된다. 그래프에 음의 가중치를 가진 사이클이 있거나, 무향 그래프에 음의 가중치를 가진 간선이 있으면 만들 수 없다.

최단 경로 트리는 루트가 있는 트리이다.

최단 경로 알고리즘

그래프	알고리즘	시간
음의 무게를 가진 간선이 없는 그래프	다익스트라	$O(m\log n)$ or $O(n^2)$
음의 무게를 가진 간선이 있는 방향 그래프	벨만-포드	$O(nm)$
비가중그래프	BFS	$O(n+m)$
DAG (유향 비순환 그래프)	위상 순서	$O(n+m)$

다익스트라^Dijkstra 알고리즘

정점 $s$로부터 정점 $v$의 거리는 $s$와 $v$ 사이의 최단 경로의 길이로 정의된다. 다익스트라 알고리즘은 출발정점 $s$로부터 다른 모든 정점까지의 거리를 계산한다.

이때, 그래프가 연결되어 있고, 간선들이 무향이며 가중치가 음수가 아님을 전제로 한다.

$s$로부터 시작하여 정점들을 차례로 배낭에 넣다가, 결국 모든 정점을 배낭에 넣는데 이때, 각 정점 $v$에 라벨 $d(v)$를 저장하여, 배낭과 인접 정점들을 구성하는 부그래프에서 $s$로부터 $v$까지의 거리를 표현한다.

반복의 각 회전에서, 배낭 밖의 정점 가운데 거리 라벨 $d$가 최소인 정점 $u$를 배낭에 넣고, $u$에 인접한 정점들의 라벨을 갱신한다.

우선순위 큐에 배낭 밖의 정점들을 보관하는데, 거리 $d$를 키값으로 한다. 각 정점 $v$에 $d(v)$와 우선순위 큐에서 $v$의 위치를 나타내는 위치자를 저장한다.

def dijkstraShortestPath(G, s):
    for v in G.vertices:
        d(v) = np.inf #일단 가장 큰 값 넣어놓고
    d(s) = 0 # 시작점->시작점 거리
    Q = generatePQ(G) # 모든 G의 노드들과 라벨 d를 담은 우선순위 큐
    while not isEmpty(Q):
        u = Q.removeMin()
        for e in u.incidentEdges:
            z = opposite(G, u, e) # 노드 u에서 간선 e의 반대편의 노드
            if z in Q.elem: # z가 우선순위 큐 안에 존재하면 (아직 경로에 포함 안된 경우)
                if d(u) + w(u, z) < d(z): # z까지의 거리보다 u에서 z로 가는게 더 짧으면
                    d(z) = d(u)+w(u, z) # 거리를 최단경로로 갱신
                    Q.replaceKey(z, d(z)) # 원소 z의 키를 d(z)로 대체
# 알고리즘이 완료되면, 모든 원소의 d값이 s로부터의 거리가 됨

다익스트라 알고리즘은 탐욕법이다. 이는 모순법으로 증명 가능하다.
만약 어떤 정점 $F$의 거리가 알고리즘 내에서 최초로 잘못 처리되었다고 가정할 때, $F$는 이전 노드 $D$까지의 거리를 기반으로 계산된 결과이다. $D$까지의 계산은 완벽히 수행되었고, $F$가 처음 에러가 발생한 노드라고 하였는데, $F$가 잘못 계산되기 위해선 $D$가 잘못 계산되었어야 하므로 다익스트라 알고리즘은 항상 정확하다.

다익스트라 알고리즘 분석

인접 간선을 각 정점에 대해 한번씩 확인한다. 정점 $z$의 거리와 위치자 라벨을 $O(deg(z)$번 읽고 쓴다. 라벨을 읽고 쓰는데는 $O(1)$시간이 걸린다.

우선순위 큐를 힙으로 구현할 경우, 각 정점이 우선순위 큐에 한번 삽입되고 한번 삭제되며 각각 $O(\log n)$시간 소요되고, 우선순위 큐 내의 정점 $z$의 키는 최대 $deg(z)$번 갱신되며 각각의 키 갱신에 $O(\log n)$시간 소요된다.

그래프가 인접리스트 구조로 표현된 경우, 다익스트라 알고리즘은 $O((n+m)\log n)$시간에 수행된다. 그래프가 연결되었으므로, 실행시간은 $O(m\log n)$으로 표시 가능하고, 그래프가 단순하다고 전재하므로, 이는 최악의 경우 $O(n^2\log n)$시간이다.

우선순위 큐를 무순리스트로 구현할 경우, 각 정점은 우선순위 큐에 한번 삽입되고 삭제되며, 삽입 삭제에 각각 $O(1), O(n)$시간이 소요된다. 우선순위 큐 내의 정점 $z$는 최대 $deg(z)$번 갱신되며, 각각의 갱신에 $O(1)$시간 소요된다.

그래프가 인접리스트로 표현된 경우, $O(n^2 + m)$시간에 수행된다. 그래프가 단순하다고 전재하므로 이는 $O(n^2)$로 단순화 가능하다.

결과적으로 우선순위 큐를 힙으로 구현하면 $O(m \log n)$시간, 무순리스트로 구현하면 $O(n^2)$시간이 소요되는데, 상수적 요소로 보면 비슷하다. 다만 최악의 경우를 고려할 때, 희소그래프 ($m<n^2 / \log n$)에 대해서는 힙 구현이, 밀집그래프 ($m>n^2 / \log n$)에 대해서는 무순리스트 구현이 유리하다.

음의 가중치 다루기

다익스트라 알고리즘은 음의 가중치를 가진 그래프에서 동작하지 않는다. 음의 가중치를 가진 싸이클이 다른 경로들의 무게 값을 헷갈리게 하기 때문이다.

이를 해결하기 위해, 음의 가중치를 가진 간선의 절댓값 $k$를 모든 가중치에 더해 음수 가중치를 없애줄 수 있다. 음의 가중치가 없는 상태로 최단 경로를 구한 후, 다시 $k$를 빼주면 된다.

벨만-포드^Bellman-Ford 알고리즘

벨만 포드 알고리즘은 음의 가중치를 갖는 간선이 있더라도 작동한다. 그래프의 간선을 방향 간선으로 전제하는데, 그렇지 않으면 음의 가중치를 가진 싸이클이 생기기 때문이다.

$O(nm)$의 실행시간을 가지며, 인접정보를 사용하지 않으므로 간선 리스트 구조 그래프에서도 수행할 수 있다.

def bellmanFordSP(G, s):
    for v in G.vertices:
        d(v) = np.inf
    d(s) = 0
    for i in range(1, n): # 1부터 n-1
        for e in G.edges: # 모든 간선에 대한 완화를 시도
            u = G.origin(e) # 간선 e의 출발 노드
            z = G.opposite(u, e) # s부터 z까지의 거리
            d(z) = min(d(z), d(u) + w(u, z))

DAG에서의 최단 경로

음의 무게를 가진 간선이 있더라도, 싸이클이 없으므로 잘 작동한다. 위상순서를 이용하여 최단 경로를 계산하는데, 별다른 데이터 구조를 사용하지 않고 다익스트라 알고리즘보다 훨씬 빠른 $O(n+m)$시간에 수행된다.

def DAGSP(G, s):
    for v in G.vertices:
        d(v) = np.inf
    # G의 노드들을 위상순서대로 정렬한 v
    d(s) = 0
    for i in range(1, n): # 1 to n-1
        for e in G.outIncidentEdges(v[i]):
            z = G.opposite(v[i], e)
            d(z) = min(d(z), d(v[i]) + w(v[i], z))

모든 쌍 최단경로 문제

가중 방향그래프 $G$의 모든 정점쌍 간의 거리를 찾는 문제

그래프에 음의 무게를 가진 간선이 없다면, 다익스트라 알고리즘을 $n$회 호출하면 된다. $O(nm\log n)$

그래프에 음의 무게를 가진 간선이 있다면, 벨만-포드 알고리즘을 $n$회 호출한다. $O(n^2m)$

동적프로그래밍을 사용하면, $O(n^3)$시간에 수행가능하다.

def allPairsSP(G):
    # v[i]가 G의 i번째 노드라 하자
    for i in range(1, n+1): # 1 to n
        for j in range(1, n+1):
            if i == j:
                D[i, j] = 0
            elif (v[i], v[j]) in G.edges:
                D[i, j] = w((v[i], v[j]))
            else:
                D[i, j] = np.inf
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                D[i,j] = min(D[i,j], D[i, k] + D[k, j])