[알고리즘] 최단경로 알고리즘 :: 늦깎이 IT

[최단 경로란?]

최단 경로 (shortest path)는 정점 u와 v를 잇는 경로 중, 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다.

노드 u에서 v까지의 최단 경로의 값을 δ(u, v)라고 하자.

[최단 경로의 유형]

1. Single-Source ( One-to-All )

• 하나의 출발 노드 s로부터 그래프 내의 모든 노드들까지의 최단 경로를 찾는 문제.

2. Single-Destination 

• 그래프내의 모든 노드로부터 하나의 목적지 노드 d까지의 최단 경로를 찾는 문제.
• 만약, 그래프가 무방향 그래프라면 Single-Source 문제와 Single-Destination 문제는 똑같은 문제가 된다.
• 그러나, 그래프가 방향 그래프라면 모든 간선들의 방향을 거꾸로 뒤집는다면, Single-Source문제와 똑같은 문제가 된다.

3. Single-Pair ( One-to-One)

• 주어진 하나의 출발 노드 s로부터 하나의 목적지 노드 t까지의 최단 경로를 찾는 문제.

4. All-Pairs ( All-to-All )

• 모든 노드 쌍에 대해서 최단 경로를 찾는 문제.

[ 최단 경로와 음수 가중치 ]

알고리즘에 따라 음수 가중치가 있어도 작동하는 경우도 있고 그렇지 않은 경우도 있다.

뒤에 살펴볼 다익스트라 알고리즘은 그래프의 모든 간선들의 가중치가 음수가 아니라는 전제조건을 갖는다.

또한, 음수 사이클이 존재할 경우 최단 경로가 존재하지 않는다. 아래 그림을 보자.

아래 그림과 같은 경우 노드 h → i → j → h 경로를 순회하다보면 각 노드까지의 가중치가 점점 줄어드는 것을 알 수 있다. 각 노드를 순회할때마다 가중치의 합이 줄어든다는 것은 실생활에서 가능하지 않다.

그러나, 그래프에 음수 사이클이 존재한다고 해서 최단경로가 절대로 존재하지 않는 것은 아니다.

예를 들어, 노드 u, v간의 최단경로인 δ(u, v)를 구하는 과정에서 음수 사이클을 지나지 않는 답이 존재할 수 있다.

[ 최단 경로의 중요한 속성 ]

노드 u와 v를 연결하는 최단 경로가 존재할 때, 이 최단 경로의 부분 경로 또한 최단 경로이다.

위의 그림처럼, 노드 u와 v를 잇는 최단 경로 (굵은 빨간선)이 있다면, 그 경로에 속해있는 노드 x와 y간의 경로 또한 최단경로이다.

[ Single-Source 최단 경로 ]

하나의 출발 노드 s로부터 그래프 내의 모든 노드들까지의 최단 경로를 찾는 문제를 알아보자.

음수 사이클이 없는 가중치 방향 그래프 G = (V, E)와 출발 노드 s ∈ V가 입력으로 주어진다고 했을 때,

각 노드 v ∈ V에 대해서 다음을 계산한다.

• 처음에는 d[s] = 0, d[v] = ∞ 로 초기화한다. d[v] 값은 시작 노드 s로부터 임의의 노드 v까지의 최단 경로이다.
• 알고리즘이 진행되면서 d[v]의 값을 갱신해나간다. 항상 d[v] ≥ δ(s, v)를 유지한다.
• 최종적으로는 d[v] = δ(s, v)가 된다.
• 또한, 노드 s에서 v까지의 최단경로상에서 v의 직전 노드(predecessor)를 π[v]라고 한다. π[v]= null로 초기화한다

[ Edge Relax ]

최단 경로를 구하는 알고리즘은 Edge Relax라는 연산을 기본 연산으로 한다. 

Relax 연산은 임의의 간선 e(u, v)에 대해서 수행한다.

그림 (a)를 살펴보자. 노드 u와 v를 잇는 간선을 e(u, v), 그 간선의 가중치를 w(u, v)라 하자.

그림 (a)에서는 d[u] = 5이고 d[v] = 9이다. 이 뜻은 현재 시점에, 출발 노드 s로부터 노드 u와 v까지의 최단 경로가 각각 5와 9라는 것이다.

노드 v의 입장에서 살펴보면, 현재 d[v] = 9 이지만, 노드 u와의 관계를 살펴보면 d[v] ＞d[u] + w(u, v)인 것을 알 수 있다. 그러므로, d[v] = d[u] + w(u, v)로 갱신된다. 반면, 그림 (b)를 살펴보면, d[v] ＜ d[u] + w(u, v) 이므로, d[v]값은 갱신되지 않는다.

이처럼, Relax 연산은 어느 한 간선 e(u, v)에 대해서 각 노드들의 d[v]값을 갱신하는 연산을 한다.

[ 일반적인 최단경로 알고리즘 동작 과정 ]

• 대부분의 Single-Source 최단경로 알고리즘은 아래와 같은 과정을 거친다.
• d[s] = 0, 노드 v ≠ s에 대해서 d[v] = ∞,  π[v]= null로 초기화한다.
• 모든 간선 e ∈ E에 대해서 Relax 연산을 수행한다.

다익스트라 알고리즘이나 벨만-포드 알고리즘 등과 같은 세부적인 최단 경로 알고리즘의 차이는 어떤 간선에 대해서, 어떤 순서로 Relax을 하느냐에 차이가 있다.

일반적인 최단 경로 알고리즘의 의사 코드를 살펴보자.

INITIALISE-SINGLE-SOURCE(G,s) 함수를 통해 초기화를 진행한다.

그 다음, 노드 v ∈ V의 값이 갱신되지 않을 때 까지, 모든 간선 e ∈ E에 대해서 Relaxation 연산을 수행한다.

위의 의사 코드에서 노드의 갯수를 N이라고 했을 때, repeat-until 반복문은 최대 N-1번 수행된다. 아래 그림을 보자.

출발 노드 s에서 v까지의 최단 경로 δ(s, v)를 구한다고 가정해보자.

repeat 반복문이 한번 수행될 때 마다 최소 하나의 임의의 노드 v에 대한 d[v] 값이 정해지는 것을 알 수 있다.

따라서, 노드의 갯수가 N개 일때, 간선의 갯수는 N - 1개 이므로 repeat-until 반복문 또한 최대 N - 1 번 수행된다.

[ 벨만-포드 알고리즘 ]

 벨만-포드 알고리즘은 Relax 연산의 수행 횟수를 정해놓은 것이다. 위처럼 노드 u에서 v로 가는 최단 거리 δ(u, v)를 구하기 위해서는 노드u와 v사이에 있는 간선들의 갯수만큼 Relax 연산을 수행하면 된다.

[ 의사 코드 ]

INITIALISE-SINGLE-SOURCE(G,s) 함수를 통해 초기화를 진행한다.

그 다음, 노드의 갯수를 N이라고 할 때 N - 1번 반복문을 수행하면서 모든 간선 e ∈ E에 대해서 Relaxation 연산을 수행한다.

반복문이 끝나고 난 뒤, 다시 한번 모든 간선에 대해서 갱신이 일어나는지 확인한다. 이때, 갱신이 될 수 있다는 것은 음수 사이클이 존재한다는 뜻이다.

[ 다익스트라 알고리즘 ]

다익스트라 알고리즘은 Single-Source 최단경로 문제이다.

일반적인 최단 경로 알고리즘에서는 repeat-until 반복문을 relax 연산을 하더라도 변화가 없을 때 까지 진행한다고 설명했다. relax연산에 대한 조건이 따로 없기 때문에, 임의의 노드 u, v에 대한 간선 e(u ,v)에 대해서 relax연산이 중복될 수 있다.

반면, 다익스트라 알고리즘은 위에서 설명한 Edge Relax 연산의 순서를 정한 알고리즘이라고 생각하면 된다. 다익스트라 알고리즘은 모든 간선들에 대해서 relax 연산을 수행하는 것이 아니라 relax 연산을 진행하지 않은 간선들 중에서 선택적으로 relax 연산을 진행하는 것이다.

[ 다익스트라 알고리즘 동작 원리 ]

• 최단 경로를 찾은 노드들을 저장하는 집합 S와 거리를 나타내는 d 배열을 선언하고, 이때 S 집합은 공집합, d의 모든 값은 ∞로 초기화한다.
• d의 값 중에 가장 작은 값을 출발 노드로 지정한다. 이때 d[x] 가 의미하는 것은 현재까지 찾은 경로들 중, 출발노드로부터 x까지의 최단거리를 나타낸다. d[x] = 3이라는 것은 출발 노드로부터 x까지의 현재까지 찾은 최단경로를 의미한다.
• 출발 노드로부터 뻗어 나가는 간선들에 대해 relax 연산을 수행한다. 
• 어느 한 노드 x로부터 뻗어 나가는 모든 간선들에 대해서 relax 연산을 수행했다면, 노드 x를 집합 S에 추가한다.
• 이후, 다시 d 배열에서 집합 S에 속하지않고, 최소 값 갖는 노드를 출발 노드로 지정한 후 반복한다.

아래 그림을 보자.

그림 (a)에서 출발 노드 s를 설정하고, 이 노드로부터 나가는 간선 e(s, t)와 e(s, y)에 대해 relax 연산을 수행한다.

그림 (b)에서 relax 연산을 수행 후, 노드 d[t] = 10, d[y] = 5로 바뀐 것을 알 수 있다. 이때, 노드 s는 더 이상 확인할 필요가 없음을 유의한다. 그림 (c)에서 relax 연산 이후, d 배열을 살펴보면서 d 값이 가장 작은 노드 y를 출발 노드로 지정한다.

그림 (d)를 보면, 노드 y로부터 뻗어나가는 간선 e(y, t)와 e(y, z), e(y, x)에 대해서 relax 연산을 함으로써 d[t] = 5, d[z] =7, d[x] =14로 갱신됨을 확인 할 수 있다. (d) [그림에서는 d[x] = 14로 갱신되는 것이 생략되었다. ]그 이후, d 값이 최소인 노드 z부터 뻗어나가는 간선 e(z, x)에 대해 relax 연산을 수행한다. 그림 (e)를 보면 d 값이 최소인 노드 t로부터 뻗어나가는 간선 e(t, x)에 대해 relax 연산을 수행함으로써 d[x] = 9로 갱신됨을 확인할 수 있다. 마지막으로 그림 (f)를 보면 노드 x에서 뻗어나가는 간선 e(x, z)에 대해서 relax 연산을 수행하려고 하지만, 이미 노드 z는 이전에 확인했으므로 건너뛴다.

모든 노드들에 대한 확인이 끝났으므로, 종료한다.

다익스트라 알고리즘에서 핵심이 되는 연산은 집합 S에 임의의 노드 x가 추가되었다면 노드 x에 인접한 모든 노드들에 대해서 d 값을 갱신해야하는 것이다. 아래 그림을 보자.

예를 들어, 노드 u가 집합 S에 추가 되었다면, 노드 u와 인접한 노드인 노드 v에 대해서 d 값을 갱신하여야 한다.

[ 의사 코드 ]

Dijkstra(G, w, s)
    for each u ∈ V do
        d[u] = ∞
        π[u] = null
    end
    
    S ← ∅
    d[s] ← 0
 
    while |S| < N do
        find u ∉ S with the minimum d[u]
        S ← S U {u}
        for each v ∉ S adjacent to u do
            if d[v] > d[u] + w(u, v) then
                d[v] ← d[u] + w9u, v)
                π[v] ← u
            end
        end
    end        

2~5)번 라인에서는 초기화를 수행한다.

7)번 라인에서는 집합 S를 공집합으로 초기화한다.

8)번 라인에서는 출발 노드 s에 대해서 d값을 0으로 설정한다.

10)번 라인에서는 집합 S의 크기가 N까지 될 때 while문을 반복한다.

11)번 라인에서는 집합 S에 속하지 않은 노드들 중 d 값이 가장 작은 노드 u를 선택한다.

12)번 라인에서는 노드 u를 집합 S에 포함시킨다.

13)번 라인에서는 노드 u에 인접한 모든 노드들 v에 대해서 d 값을 갱신한다.

[ 시간 복잡도 ]

모든 노드에 대한 d 값을 초기화하는 시간 복잡도는 O(N)이다.

while 반복문은 N - 1번 반복하므로 시간 복잡도는 O(N)이다.

집합 S에 속하지 않는 노드들 중 d 값이 최소인 노드 u를 찾는 시간 복잡도는 최대 O(N)이다.

노드 u에 인접한 모든 노드들을 방문하는 시간 복잡도는 O(degree(u))이므로 O(N)이다.

relax 연산에 걸리는 시간 복잡도는 O(1)이다.

즉, 전체 시간 복잡도는 O(N) + O(N * (N + N)) = O(N^2) 이다.

[ 더 생각해보기 ]

다익스트라 알고리즘의 시간 복잡도는 사실 프림의 알고리즘과 거의 유사하다고 보면된다. 프림의 알고리즘은 [이곳] 을 참고하기 바란다.

간단히 설명하면, 우선순위 큐를 활용하면 집합 S에 속하지 않은 노드들에 대해서 d 값을 최소로 갖는 노드를 찾아야 하는 과정을 O(logN)만큼의 시간 복잡도를 갖게할 수 있다.

[ 의사 코드 ]

DIJKSTRA(G, w, r) // r은 시작 노드
    for each v ∈ V do
        d[v] = ∞
    end
    S ← ∅
    d[r] ← 0
    Q ← r
 
    while Q != ∅
        u ← EXTRACT-MIN(Q)
        S ← S U {u}
        for each v adjacent to u
            do RELAX(u, v, w)

2~3)번 라인에서 초기화를 진행한다.

6~7)번 라인에서 시작 노드 r에 대한 d값을 0으로 설정하고 시작 노드를 큐에 넣는다.

9)번 라인에서 큐가 공집합이 될 때까지 반복한다.

10)번 라인에서 d 값을 최소로 갖는 노드 u를 찾는다.

11)번 라인에서 집합 S에 노드 u를 포함시킨다.

12)번 라인에서 노드 u와 인접한 모든 노드들에 대해서 relax 연산을 수행한다.

[ 시간 복잡도 ]

그래프 G에 포함된 노드의 갯수를 N, 간선의 갯수를 M개라고 하자.

초기화하는 시간 복잡도는 O(N)이다.

while 반복문은 N번 반복하므로 시간 복잡도는 O(N)이다.

최소 힙에서 최소 값을 갖는 노드 u를 찾는 시간 복잡도는 O(logN)이다.

모든 노드들에 대해서 인접한 모든 노드들을 확인해야 하므로, 8)번 라인의 시간 복잡도는 아래 식을 만족한다.

relax 연산의 시간 복잡도는 O(logN)이다. 이를 통해 모든 노드들에 대해서 인접한 모든 노드들을 확인하는 시간 복잡도 O(M)동안 relax 연산을 해야 하므로 O(MlogN)만큼의 시간이 걸린다는 것을 알 수 있다.

즉, 전체 시간 복잡도는 O(NlogN + MlogN) = O(MlogN)이다.

[ JAVA 코드 ]

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
 
public class Dijkstra {
 
    static int N = 6;
 
    public static void main(String[] args) {
 
        Graph graph = new Graph(N);
        graph.addEdge(1, 2, 5);
        graph.addEdge(1, 5, 10);
        graph.addEdge(2, 5, 3);
        graph.addEdge(2, 3, 2);
        graph.addEdge(2, 4, 9);
        graph.addEdge(3, 1, 7);
        graph.addEdge(3, 4, 6);
        graph.addEdge(4, 3, 4);
        graph.addEdge(5, 2, 2);
        graph.addEdge(5, 4, 1);
 
        dijkstra(graph.adj, 1);
    }
 
    public static void dijkstra(List<List<Node>> adj, int source) {
 
        int[] dist = new int[adj.size()];
        boolean[] spt = new boolean[adj.size()];
        PriorityQueue<Node> q = new PriorityQueue<>();
 
        for (int i = 1; i < adj.size(); i++)
            dist[i] = Integer.MAX_VALUE;
 
        dist[source] = 0;
        q.offer(new Node(source, 0));
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
            if (dist[node.node] < node.weight)
                continue;
 
            spt[node.node] = true;
 
            for (int i = 0; i < adj.get(node.node).size(); i++) {
 
                Node adjNode = adj.get(node.node).get(i);
 
                if (!spt[adjNode.node]) {
 
                    if (dist[node.node] + adjNode.weight < dist[adjNode.node]) {
                        dist[adjNode.node] = dist[node.node] + adjNode.weight;
                        q.offer(new Node(adjNode.node, dist[adjNode.node]));
                    }
                }
            }
        }
 
        for (int i = 1; i < adj.size(); i++) {
            System.out.println(source + " -> " + i + " : " + dist[i]);
        }
    }
}
 
class Graph {
 
    int size;
    List<List<Node>> adj = new ArrayList<>();
 
    public Graph(int size) {
 
        this.size = size + 1;
        this.adj = new ArrayList<>();
 
        for (int i = 0; i < this.size; i++) {
            List<Node> list = new ArrayList<>();
            adj.add(list);
        }
    }
 
    public void addEdge(int src, int dest, int weight) {
        adj.get(src).add(new Node(dest, weight));
    }
}
 
class Node implements Comparable<Node> {
    int node;
    int weight;
 
    public Node(int node, int weight) {
        this.node = node;
        this.weight = weight;
    }
 
    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}

[ 플로이드-와샬 알고리즘 ]

플로이드-와샬 알고리즘은 모든 노드 쌍들간의 최단 경로를 구하는 All-Pairs 알고리즘이다. 플로이드-와샬 알고리즘은 가중치가 음이거나 양인 그래프에 대해서 최단거리를 찾는다. 또한, 동적 계획법을 기초로 하는 알고리즘이다.

플로이드-와샬 알고리즘은 임의의 노드 i와 j간의 최단거리를 구하기 위해 i, j를 거쳐가는 모든 중간 정점들을 대입하여 가장 작은 값을 찾는다.

위의 식이 나타내는 뜻은 중간에 노드집합 {1, 2, ..., k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단 경로를 뜻한다.

k = 0일 때, 노드 i에서 j까지 가기 위해 어떠한 노드도 거치지 않고 가는 최단 경로는 노드 i와 j를 잇는 가중치와 같다.

만약 노드 i와 j를 잇는 간선이 존재하지 않는다면, ∞이다.

k >= 1일 때, 중간 노드집합 {1, 2, ... , k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단 경로는 노드 k를 지나는 경우와 노드 k를 지나지 않는 경우가 있다.

또한, 위의 식을 변형하면 다음과 같다.

좌변은 노드 i에서 k까지 경로에서 중간 노드집합 {1, 2, ..., k} 를 거쳐가는 최단 경로이다. 여기서 노드 k는 도착노드이므로, 노드 i에서 k까지 가기위해 선택하는 중간 노드집합은 {1, 2, ..., (k-1)}과 같다. 그러므로 위의 식이 성립되므로 다시 식을 정리하면 아래와 같다.

[ 의사 코드 ]

FLOYD-WARSHALL(G)
    for i ← 1 to n
        for j ← 1 to n
            d[i, j] ← w(i, j)
            π[i, j] ← null
 
    for k ← 1 to n
        for i ← 1 to n
            for j ← 1 to n
                if d[i, j] > d[i, k] + d[k, j] then
                    d[i, j] ← d[i, k] + d[k, j]
                    π[i, j] ← k
 
 
PRINT-PATH(s, t, π) // s는 출발노드, t는 도착노드, π는 중간노드를 저장한 배열
    if π[s, t] == null then
        return
 
    PRINT-PATH(s, π[s, t], π)
    print(π[s, t])
    PRINT-PATH(π[s, t], t, π)

1~5)번 라인에서 d값과 π값을 초기화한다. π[i, j]값은 노드 i에서 j까지 가기위해 거쳐가는 노드를 뜻한다.

7~9)번 라인에서 1부터 N까지 반복을 수행한다.

10)번 라인에서 노드 k를 거치지않고 노드 i에서 j까지 가는 거리와 노드 k를 비교하여 갱신한다.

12)번 라인에서 노드 i에서 j까지 가기위해 거쳐가는 노드 k를 π값에 저장한다.

15)번 라인의 PRINT-PATH 함수는 노드 s에서 t까지 가는 경로를 출력하는 함수이다.

16~17)번 라인에서 노드 s에서 t까지 가는 동안 중간 노드가 없다면 종료한다.

19~21)번 라인에서 PRINT-PATH 함수를 재귀적으로 호출한다.

[ 시간 복잡도 ] 

 시간 복잡도는 3중 반복문으로 O(N^3) 만큼이 걸린다.

[ JAVA 코드 ]

import static java.lang.String.format;
 
public class FloydWarshall {
 
    final static int INF = 100000000;
    static int N;
 
    static int[][] graph = { { 0, 5, INF, 8 }, { 7, 0, 9, INF }, { 2, INF, 0, 4 }, { INF, INF, 3, 0 }, };
 
    public static void main(String[] args) {
 
        N = graph.length;
        int[][] dist = new int[N][N];
        int[][] prev = new int[N][N];
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dist[i][j] = graph[i][j];
                prev[i][j] = -1;
            }
        }
 
        floydWarshall(dist, prev);
        System.out.println("   pair     dist     path");
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i != j) {
                    System.out.print("[" + (i + 1) + " -> " + (j + 1) + "]    ");
                    System.out.print("[" + dist[i][j] + "]     ");
                    System.out.print((i + 1) + " -> ");
                    printResult(i, j, prev);
                    System.out.println((j + 1));
                }
            }
        }
    }
 
    public static void floydWarshall(int[][] dist, int[][] prev) {
 
        for (int k = 0; k < N; k++)
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    if (dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        prev[i][j] = k;
                    }
    }
 
    public static void printResult(int source, int dest, int[][] prev) {
 
        if (prev[source][dest] == -1)
            return;
        
        int pNode = prev[source][dest];
        printResult(source, pNode, prev);
        System.out.print((pNode + 1) + " -> ");
        printResult(pNode, dest, prev);
    }
}
 

[ 입력 ]

입력의 출처는 [나동빈]님의 블로그를 참조하였음.

[ 출력 ] 

   pair     dist     path
[1 -> 2]    [5]     1 -> 2
[1 -> 3]    [11]     1 -> 4 -> 3
[1 -> 4]    [8]     1 -> 4
[2 -> 1]    [7]     2 -> 1
[2 -> 3]    [9]     2 -> 3
[2 -> 4]    [13]     2 -> 3 -> 4
[3 -> 1]    [2]     3 -> 1
[3 -> 2]    [7]     3 -> 1 -> 2
[3 -> 4]    [4]     3 -> 4
[4 -> 1]    [5]     4 -> 3 -> 1
[4 -> 2]    [10]     4 -> 3 -> 1 -> 2
[4 -> 3]    [3]     4 -> 3