가중치가 부여된 방향성 비순환 그래프(Directed Acyclic Graph, DAG)와 하나의 시작 정점(source vertex)이 주어졌을 때, 시작 노드에서 그래프 내 모든 다른 정점까지의 최장 거리를 구하는 문제를 다룹니다.
DAG에서 최장 경로를 효율적으로 찾으려면 위상 정렬(Topological Sort)을 활용해야 합니다. 위상 정렬의 결과는 스택에 저장되며, 이후 스택에서 정점을 하나씩 꺼내면서 각 정점에 대한 최장 거리를 계산하게 됩니다.
입력과 출력
그래프는 인접 행렬 형태의 비용 행렬(cost matrix)로 주어집니다. 간선이 존재하지 않는 경우는 음의 무한대(-∞)로 표시합니다.
입력: 그래프의 비용 행렬 0 5 3 -∞ -∞ -∞ -∞ 0 2 6 -∞ -∞ -∞ -∞ 0 7 4 2 -∞ -∞ -∞ 0 -1 1 -∞ -∞ -∞ -∞ 0 -2 -∞ -∞ -∞ -∞ -∞ 0 출력: 시작 정점 1로부터의 최장 거리 Infinity 0 2 9 8 10
출력 결과를 보면, 시작 정점(1번)에서 도달할 수 없는 정점은 Infinity로 표시되고, 나머지 정점들은 최장 거리 값이 출력됩니다.
알고리즘
topoSort(u, visited, stack)
입력: 시작 노드 u, 방문 여부를 추적하는 visited 리스트, 스택
출력: 노드들을 위상 정렬 방식으로 정렬
Begin
u를 방문 처리
u와 연결된 모든 정점 v에 대해:
v를 아직 방문하지 않았다면
topoSort(v, visited, stack) 재귀 호출
u를 스택에 push
EndlongestPath(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] 출력
EndC++ 구현 예제
#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 longestPath(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 << "Longest Distance From Source Vertex "<<start<<endl;
longestPath(start);
}실행 결과
Longest Distance From Source Vertex 1 Infinity 0 2 9 8 10
동작 원리 정리
이 알고리즘의 핵심은 다음과 같습니다.
1. 위상 정렬 수행: DFS 기반 위상 정렬을 통해 그래프의 정점들을 의존 관계 순서대로 스택에 저장합니다. 스택에서 꺼내는 순서가 곧 위상 순서(topological order)가 됩니다.
2. 위상 순서대로 완화(Relaxation): 스택에서 정점을 하나씩 꺼내며, 해당 정점에서 도달 가능한 인접 정점들의 거리를 갱신합니다. 더 긴 경로를 발견하면 거리 값을 업데이트합니다.
3. 결과 출력: 시작 정점에서 도달할 수 없는 정점은 Infinity로, 도달 가능한 정점은 계산된 최장 거리를 출력합니다.
일반적인 그래프에서 최장 경로 문제는 NP-hard로 알려져 있지만, 사이클이 없는 DAG에서는 위상 정렬을 활용하면 O(V+E) 시간 복잡도로 선형 시간 안에 해결할 수 있다는 점이 이 알고리즘의 큰 장점입니다.