Shortest Paths 문서 원본 보기

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[알고리즘 설계와 분석#문제|알고리즘 설계와 분석]] 

==개요==
해당 문서에서는 [[Graph|그래프]]에서의 최단 경로(shortest path)를 찾는 알고리즘을 설명한다.

==Applications for Shortest Paths==
[[파일:Figure 1. Sentence Disambiguation .png|섬네일|Figure 1. Sentence Disambiguation ]]
그래프 상 두 노드 간 최단 경로를 찾는 문제는 실제 여러 분야에서 나타나며, 아래와 같다:
* 교통 문제(Transportation problems): 두 지점 사이의 가장 저렴하거나 빠른 이동 경로를 찾는 문제
** 대표적인 사례가 네트워크 라우팅이며, 이는 [[Routing Algorithms#LS routing algorithm|LS 라우팅 알고리즘]] 문서에서 자세히 확인할 수 있다.
* 이동 계획(Motion planning): 로봇이나 캐릭터가 장애물을 피해 이동하는 경로를 구하는 문제.
* 통신 문제(Communications problems): 두 노드 간 신호 전송이 가장 빠른 경로를 찾는 문제
또한, 자연어 처리에 최단 경로 문제를 응용할 수 있다. 숫자키를 이용하여 문자를 입력하고자 할때, 여러 단어 후보가 생긴다. 예를 들어 4483을 입력한다면 가능한 단어는 “give” 또는 “hive”이다. 이때 각 가능한 단어를 정점(vertex) 으로, 단어 간 가능한 연결 관계를 간선(edge) 으로 표현할 수 있다. 따라서 최단 경로 문제를 활용하여 문장 해석을 하는 것은, 가능한 후보 중 의미적으로 가장 자연스러운 조합(=가장 짧은 경로) 를 찾는 과정이다. 이 과정은 figure 1에 잘 나타나 있다. 이때 그래프에는 간선(단어 간 연결)에 “확률 기반 가중치(weight)”를 부여해야 한다. 이는 두 단어가 문장에서 인접할 확률을 기반으로 한다. 이 경우에는 Dynamic Programming 또는 Viterbi 알고리즘을 사용해 DAG(Directed Acyclic Graph) 내에서 최소 가중치 경로를 찾아야 한다.

==Kind of Shortest Paths Problem==
최단 경로 문제의 가장 기본적인 형태는 가중치 그래프(weighted graph)에 대한 것이다. 그 이유는 가중치 그래프에 대한 최단 경로가 도로 문제 등 다양한 문제에서 활용될 수 있기 때문이다. 하지만 최단 경로 문제는 그래프의 특성에 따라 여러 가지 고려할 점이 존재하며, 해당 문단에서는 이에 대해 설명한다.

===Unweighted Graphs===
비가중 그래프(Unweighted Graph)는 모든 간선의 비용이 동일한 그래프를 의미한다. 따라서 비가중 그래프에서의 최단 경로는 가장 적은 간선을 지나는 경로이다. 이는 n개의 정점과 m개의 간선이 주어졌을 때, [[BFS|BFS(Breadth-First Search)]]로 O(n + m) 시간에 해결 가능하다. 하지만 BFS 그래프를 가중 그래프에 적용할 수는 없는데, 이는 여러 개의 작은 간선을 지나는 게 한 개의 큰 간선을 지나는 것보다 더 저렴할 수 있기 때문이다.

===Negative Edge Weights===
그래프에 대해 음수 가중치 간선(negative edge) 이 존재하면 문제가 복잡해진다. 이는 “음수 가중치 순환(negative cycle)”이 있으면, 무한히 돌면서 비용을 계속 줄일 수 있어 최단 경로가 정의되지 않기 때문이다. 예를 들어, A → B → C → A 로 돌아오는데 합이 -3이라면 계속 순환할수록 더 짧은 경로가 생기므로 의미 없는 결과가 된다. 따라서 일반적으로는 모든 가중치를 양수라고 설정하며, 특히 Dijkstra는 양수 가중치만 다루는 알고리즘이다. 예외적으로 Bellman-Ford 알고리즘 등은 음수 가중치를 처리할 수 있다. 이때 MST(Minimum Spanning Tree)는 음수 가중치와 상관없으므로 이에 대해 혼동하면 안된다.<ref>MST는 자체 정의에 의해서 사이클을 배제한 트리를 의미하기 때문이다.</ref>

==Dijkstra’s Algorithm==
다익스트라 알고리즘(Dijkstra’s Algorithm)은 간선의 가중치가 양수인 가중치 그래프에서의 최단 경로를 탐색하는 알고리즘이다. 다익스트라 알고리즘의 핵심 원리는 부분 최적성(Optimal Substructure)이다. 부분 최적성이란, 만약 경로 s→…→x→…→t 가 최단 경로라면, 그 일부인 s→…→x 도 역시 최단 경로여야 한다는 뜻이다. 이를 이용하여 Dynamic Programming 방식으로 접근할 수 있다. 이는 이미 구한 가까운 노드들의 최단 경로 정보를 이용해 점점 멀리 있는 노드들의 최단 경로를 확장해 나가는 구조이다.

===How Dijkstra’s Algorithm works===
다익스트라 알고리즘의 시작 단계(Initialization)에서는 출발점 s에서 각 노드까지의 거리를 초기화한다. 이는 아래와 같다:
# d(s, s) = 0 (자기 자신까지의 거리는 0)
# 나머지 노드는 무한대로 설정한<ref>다른 정점에 대한 거리를 모르기 때문이다.</ref> 후, 각 정점 s에서 연결된 간선 중 가장 짧은 간선을 이용해 인접 노드의 거리값을 갱신한다.
다익스트라 알고리즘은 시작 단계 이후, 주어진 거리 배열(distance array)를 업데이트(update)하며 최단 경로를 탐색한다. 이는 정점 s에서 어떤 정점 x에 대한 최단 경로가 확정되면, 그 노드와 연결된 모든 간선을 검사해 s→x→y 가 기존 s→y보다 짧은지 확인하고 갱신하는 방식이다. 즉, 거리 배열(distance array)을 유지하면서 새 노드를 확정할 때마다 그 이웃 노드들의 거리값을 업데이트하는 방식이다. 아래는 다익스트라 알고리즘에 대한 수도 코드이다:
<syntaxhighlight lang="go">
//initialize
known = {s}
for i = 1 to n, dist[i] = <math>\infty</math>
for each edge (s, v), dist[v] = d(s, v) //s와 연결된 정점에 대해 dist 업데이트
last = s //마지막으로 확정된 정점

//update
while (last <math>\neq</math> t) //t는 목표 정점
       select v such that dist(v) = min<sub>unknown</sub>(dist(i))
       for each edge (v, x):
           dist[x] = min(dist[x], dist[v] + w(v, x))
       last = v
       known = known <math>\cup</math> {v}
</syntaxhighlight>
[[파일:Figure 2. Dijkstra Example.png|섬네일|Figure 2. Dijkstra Example]]
위 수도 코드에서 known 집합은 “최단 경로가 확정된 정점들”을 의미한다. 이때 각 과정에서는 아직 확정되지 않은 노드 중 가장 dist 값이 작은 것을 선택하여 dist값을 확정하며, 선택된 노드의 모든 인접 노드에 대해 거리를 갱신한다. 이 과정을 반복하여 최단 경로를 탐색한다. Figure 2는 다익스트라 알고리즘을 실행한 예시 결과이다.

다익스트라 알고리즘은 [[Minimum Spanning Trees#Prim's Algorithm|Prim 알고리즘]]과 유사하다. 이는 Prim도 “가장 작은 비용으로 확장하는 구조”를 사용하며, 둘 다 “가장 가까운 정점부터 추가”라는 탐욕적(greedy) 구조를 가지기 때문이다.

다익스트라 알고리즘은 배열 자료구조를 기반으로 하는 경우 Prim 알고리즘과 마찬가지로 O(n<sup>2</sup>)의 시간 복잡도를 가진다. 이는 각 정점에 대해 아직 포함되지 않은 노드 중 최솟값을 찾기 위해 O(n) 시간이 걸리기 때문이다. 하지만 단순 배열 대신 [[Priority Queues|priority queue]]자료 구조를 사용하면 속도를 개선할 수 있다.<br>
먼저 Binary Heap(이진 힙)을 사용하는 경우, 각 정점을 현재까지의 거리 distance[v] 기준으로 정렬해두고 “가장 짧은 거리의 정점”을 O(log n) 시간에 꺼낼 수 있다. 이 경우 시간 복잡도는 아래와 같이 계산된다:
# 정점을 꺼내는 작업은 n번 일어나며, 각각 O(log(n))의 시간복잡도를 가진다. → O(n log(n))
# 거리 갱신(relaxation)은 각 간선마다 최대 한 번 일어난다. → O(m log(n))
# 총 시간 복잡도: O((n+m)log(n))
이보다 더욱 효율적인 자료구조는 Fibonacci Heap이다. Fibonacci Heap은 Binary Heap보다 더 효율적인 우선순위 큐이며, 핵심 차이점은 decrease-key 연산이 매우 빠르다는 것이다. decrease-key 연산이란 아래와 같이 다익스트라에서 어떤 간선을 완화(relaxation)할 때:
<syntaxhighlight lang="c">
if (distance[w] > distance[v] + weight(v,w))
    distance[w] = distance[v] + weight(v,w);
</syntaxhighlight>
이처럼 기존 거리보다 짧은 경로를 발견하면 힙에서 해당 정점의 키(거리값)를 줄여야 하는데, 이 연산을 decrease-key 라고 부른다. 해당 연산은 Binary Heap에서는 O(log(n))의 시간 복잡도가 소요되지만, Fibonacci Heap에서는 평균 O(1)만에 수행 가능하다. 이에 따라 시간 복잡도는 O(nlog(n)+m)이 된다.

==Dijkstra’s Implementation==
<syntaxhighlight lang="c">
int dijkstra(graph *g, int start) {
    int i;              /* counter */
    edgenode *p;        /* temporary pointer */
    bool intree[MAXV+1];/* is the vertex in the tree yet? */
    int distance[MAXV+1];/* cost of adding to tree */
    int v;              /* current vertex to process */
    int w;              /* candidate next vertex */
    int dist;           /* cheapest cost to enlarge tree */
    int weight = 0;     /* tree weight */

    for (i = 1; i <= g->nvertices; i++) {
        intree[i] = false;
        distance[i] = MAXINT;
        parent[i] = -1;
    }

    distance[start] = 0;
    v = start;

    while (!intree[v]) {
        intree[v] = true;
        if (v != start) {
            printf("edge (%d,%d) in tree \n", parent[v], v);
            weight = weight + dist;
        }

        p = g->edges[v];
        while (p != NULL) {
            w = p->y;
            if (distance[w] > (distance[v] + p->weight)) {   /* CHANGED */
                distance[w] = distance[v] + p->weight;       /* CHANGED */
                parent[w] = v;                               /* CHANGED */
            }
            p = p->next;
        }

        dist = MAXINT;
        for (i = 1; i <= g->nvertices; i++) {
            if ((!intree[i]) && (dist > distance[i])) {
                dist = distance[i];
                v = i;
            }
        }
    }

    return(weight);
}
</syntaxhighlight>

==Floyd’s Algorithm==
Floyd 알고리즘은 그래프의 모든 정점 쌍 간 최단 경로(All-Pairs Shortest Path) 를 찾는 알고리즘이다. 하나의 정점 s로부터 다른 모든 정점까지의 최단경로는 Dijkstra 알고리즘으로 구할 수 있다. 하지만 모든 정점 쌍 사이의 최단 경로를 찾기 위해서 Dijkstra를 n번 실행하면 대략 O(n<sup>3</sup>)의 시간 복잡도가 소요된다. 따라서 모든 정점 쌍 사이의 최단 경로를 더욱 효율적으로 찾고자 하는 것이 Floyd 알고리즘의 시작점이다. 

===Dynamic Programming===
Floyd 알고리즘은 동적 프로그래밍을 기반으로 한다. 동적 프로그래밍은 아래와 같은 단계를 통해 문제를 해결한다:
# 최적해의 구조를 파악한다.(Optimal Substructure)
# 그 값을 재귀적으로 정의한다.(Recurrence)
# Bottom-up 방식으로 계산한다.
# 계산된 값으로부터 최적해를 복원한다.
따라서, Floyd 알고리즘을 수행하기 위해서는 아래와 같이 인접 행렬(Adjacency Matrix)로부터 초기 거리 행렬 D를 구성해야 한다:
 <math>D[i,j]=
 \begin{cases}
 0 & if i = j \\
 w(i,j) & if edge(i, j) \in E \\
 \infty, & otherwise
 \end{cases}
 </math>
위의 식은 간선 (i,i)의 거리 D[i,i]는 0, 간선 (i, j)가 존재하면 거리 D[i,j]는 w(i,j), 간선 (i, j)가 존재하지 않으면 그 거리 D[i,j]는 무한대라는 것을 의미한다. 이때 동적 프로그래밍의 상태 정의는 아래와 같다:
* <math>d[i,j]^k</math>: 1~k번 정점만을 중간 노드로 사용할 수 있을 때, i→j의 최단거리
* 즉, k가 커질수록 고려할 수 있는 중간노드의 집합이 확장됨.
* 경로는 vertex k를 “지나거나(through k)” 또는 “지나지 않거나” 두 경우 뿐이다.
이를 기반으로 아래와 같이 점화식(Recurrence Relation)을 세울 수 있다:
 <math>d[i,j]^k=min(d[i,j]^{k-1}, d[i,k]^{k-1}+d[k,j]^{k-1})</math>
즉, 위 점화식은 “i에서 j로 갈 때 vertex k를 거치는 것이 더 짧은가?”를 확인해서 갱신하는 것이다. k를 거치지 않은 최단거리 vs k를 거치는 경로의 거리 중 더 짧은 걸 선택하고, 이렇게 k=1→n 순서로 모든 정점을 중간노드로 고려하면, 최종적으로 모든 쌍의 최단경로를 완성할 수 있다.

===Implementation of Floyd's Algorithm===
아래는 Floyd 알고리즘의 수도코드이다.
<syntaxhighlight lang="go">
d⁰ = w
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])
</syntaxhighlight>
위에서 시간복잡도는 Dijkstra n회와 복잡도는 같은 O(n<sup>3</sup>)이지만, Floyd 알고리즘은 구현이 단순하고 상수 계수가 작아 더 빠르게 작동한다. 아래는 이를 C언어로 구현한 코드이다:
<syntaxhighlight lang="c">
typedef struct {
    int weight[MAXV+1][MAXV+1];
    int nvertices;
} adjacency_matrix;

void floyd(adjacency_matrix *g) {
    int i, j, k, through_k;
    for (k = 1; k <= g->nvertices; k++) {
        for (i = 1; i <= g->nvertices; i++) {
            for (j = 1; j <= g->nvertices; j++) {
                through_k = g->weight[i][k] + g->weight[k][j];
                if (through_k < g->weight[i][j]) {
                    g->weight[i][j] = through_k;
                }
            }
        }
    }
}
</syntaxhighlight>

==각주==