방향성 비순환 그래프(DAG)의 최단 경로: 위상 정렬을 활용한 효율적인 알고리즘

가중치가 있는 하나의 방향성 비순환 그래프(Directed Acyclic Graph, DAG)와 시작 정점(source vertex)이 주어졌을 때, 시작 노드에서 그래프 내 모든 다른 정점까지의 최단 거리를 구하는 문제를 다룹니다.

일반적인 가중 그래프에서는 음수 가중치가 포함된 경우 벨만-포드(Bellman-Ford) 알고리즘을, 양수 가중치만 있는 경우 다익스트라(Dijkstra) 알고리즘을 사용할 수 있습니다. 하지만 그래프가 방향성 비순환 그래프라면 위상 정렬(Topological Sorting) 기법을 활용하여 알고리즘의 복잡도를 크게 줄일 수 있습니다.

입력과 출력

입력:
그래프의 비용 행렬(cost matrix)
0   5   3  -∞  -∞  -∞
-∞   0   2   6  -∞  -∞
-∞  -∞   0   7   4   2
-∞  -∞  -∞   0  -1   1
-∞  -∞  -∞  -∞   0  -2
-∞  -∞  -∞  -∞  -∞   0

출력:
시작 정점 1로부터의 최단 거리
Infinity 0 2 6 5 3

알고리즘

1. topoSort(u, visited, stack)

입력: 시작 노드 u, 방문 여부를 추적하는 visited 리스트, 스택(stack)
출력: 노드들을 위상 정렬 방식으로 정렬합니다.

Begin
    u를 방문 처리(visited)한다
    u와 연결된 모든 정점 v에 대해 반복:
        v를 아직 방문하지 않았다면
            topoSort(v, visited, stack) 재귀 호출
    u를 스택에 push한다
End

2. shortestPath(start)

입력: 시작 노드
출력: 시작 노드로부터 모든 정점까지의 최단 거리 리스트

Begin
    처음에 모든 노드를 미방문 상태로 초기화한다
    그래프의 각 노드 i에 대해 반복:
        i를 방문하지 않았다면
            topoSort(i, visited, stack) 호출

    모든 정점의 거리를 ∞로 초기화한다
    dist[start] := 0
    스택이 비어 있지 않은 동안 반복:
        스택에서 항목을 pop하여 nextVert에 저장
        dist[nextVert] ≠ ∞라면,
            nextVert에 인접한 각 정점 v에 대해 반복:
                cost[nextVert, v] ≠ ∞라면,
                    dist[v] > dist[nextVert] + cost[nextVert, v] 라면
                        dist[v] := dist[nextVert] + cost[nextVert, v]

    그래프의 모든 정점 i에 대해 반복:
        dist[i] = ∞이면 Infinity 출력
        아니면 dist[i] 출력
End

C++ 예제 코드

#include<iostream>
#include<stack>
#define NODE 6
#define INF 9999

using namespace std;

int cost[NODE][NODE] = {
    {0, 5, 3, INF, INF, INF},
    {INF, 0, 2, 6, INF, INF},
    {INF, INF, 0, 7, 4, 2},
    {INF, INF, INF, 0, -1, 1},
    {INF, INF, INF, INF, 0, -2},
    {INF, INF, INF, INF, INF, 0}
};

void topoSort(int u, bool visited[], stack<int>& stk) {
    visited[u] = true;              // 노드 u를 방문 처리
    for(int v = 0; v < NODE; v++) {
        if(cost[u][v]) {            // u에 인접한 모든 정점 v 검사
            if(!visited[v])
                topoSort(v, visited, stk);
        }
    }
    stk.push(u);                    // 시작 정점을 스택에 push
}

void shortestPath(int start) {
    stack<int> stk;
    int dist[NODE];

    bool vis[NODE];
    for(int i = 0; i < NODE; i++)
        vis[i] = false;             // 처음에 모든 노드를 미방문으로 설정

    for(int i = 0; i < NODE; i++)   // 각 정점에 대해 위상 정렬 수행
        if(!vis[i])
            topoSort(i, vis, stk);

    for(int i = 0; i < NODE; i++)
        dist[i] = INF;              // 초기에는 모든 거리를 무한대로 설정
    dist[start] = 0;                // 시작 정점의 거리는 0

    while(!stk.empty()) {           // 스택에 요소가 있는 동안 위상 순서대로 처리
        int nextVert = stk.top(); stk.pop();

        if(dist[nextVert] != INF) {
            for(int v = 0; v < NODE; v++) {
                if(cost[nextVert][v] && cost[nextVert][v] != INF) {
                    if(dist[v] > dist[nextVert] + cost[nextVert][v])
                        dist[v] = dist[nextVert] + cost[nextVert][v];
                }
            }
        }
    }
    for(int i = 0; i < NODE; i++)
        (dist[i] == INF) ? cout << "Infinity " : cout << dist[i] << " ";
}

main() {
    int start = 1;
    cout << "Shortest Distance From Source Vertex " << start << endl;
    shortestPath(start);
}

실행 결과

Shortest Distance From Source Vertex 1
Infinity 0 2 6 5 3

동작 원리 요약

이 알고리즘의 핵심은 다음과 같습니다.

첫째, DFS 기반의 위상 정렬을 수행하여 그래프의 모든 정점을 선행 관계에 따라 스택에 쌓습니다. 스택에서 pop되는 순서는 곧 위상 순서(topological order)와 일치하므로, 어떤 정점을 처리할 때 그 정점으로 들어오는 모든 간선은 이미 처리가 완료된 상태입니다.

둘째, 위상 순서대로 정점을 하나씩 꺼내며 해당 정점에서 나가는 간선들의 가중치를 이용해 인접 정점의 거리를 완화(relaxation)합니다. 이 과정에서 음수 가중치 간선도 문제없이 처리할 수 있습니다.

셋째, 시작 정점에서 도달할 수 없는 정점은 거리가 무한대(∞)로 남아 있으므로, 최종 결과에서 'Infinity'로 표시됩니다.

위상 정렬의 시간 복잡도는 O(V+E), 거리 완화 단계 역시 전체적으로 O(V+E)이므로, 이 알고리즘의 전체 시간 복잡도는 O(V+E)입니다. 이는 다익스트라 알고리즘의 O((V+E)logV)보다 빠르며, 벨만-포드 알고리즘의 O(V·E)보다 훨씬 효율적입니다.