DAG(방향성 비순환 그래프, Directed Acyclic Graph)에서 SSSP(Single Source Shortest Path, 단일 출발점 최단 경로)를 구하는 C++ 프로그램을 소개합니다. 이 프로그램은 다익스트라(Dijkstra) 알고리즘을 사용해 그래프의 시작 노드(0번 노드)에서 다른 모든 노드까지의 최단 경로 길이를 계산하며, 어떤 노드를 경유해서 도달하는지와 함께 각 정점까지의 최소 비용을 출력합니다.
알고리즘
다익스트라 알고리즘은 아직 방문하지 않은 노드 중 현재까지의 거리가 가장 짧은 노드를 하나씩 선택하고, 그 노드를 거쳐갈 때 더 짧아지는 경로가 있으면 거리 값을 갱신하는 방식으로 동작합니다.
시작
그래프의 요소들을 입력받는다.
함수 shortestpath():
변수 초기화
a[i] = 1 // 시작 노드 방문 표시
d[i] = 0 // 시작 노드까지의 거리
s[i].from = 0 // 경유 노드 정보
i = 0부터 3까지 반복
만약 b[0][i] == 0이면
continue
아니면
d[i] = b[0][i]
s[i].from = 0
끝
끝
while (c < 4) 반복
min = INFINITY로 초기화
i = 0부터 3까지 반복
만약 min <= d[i] 또는 d[i] == 0 또는 a[i] == 1이면
continue
아니고 min > d[i]이면
min = d[i]
끝
끝
k = 0부터 3까지 반복
만약 min == d[k]이면
t = k
break
아니면
continue
끝
끝
a[t] = 1 // 선택된 노드 방문 처리
j = 0부터 3까지 반복
만약 a[j] == 1 또는 b[t][j] == 0이면
continue
아니고 a[j] != 1이면
만약 d[j] > (d[t] + b[t][j])이면
d[j] = d[t] + b[t][j] // 더 짧은 경로로 갱신
s[j].from = t // 경유 노드 기록
끝
끝
끝
c 증가
끝
i = 0부터 3까지 반복
시작 노드에서 각 노드까지의 최소 비용 출력
끝
끝
C++ 예제 코드
#include <iostream>
using namespace std;
#define INFINITY 9999
struct node {
int from; // 어느 노드를 경유해 도달했는지 저장
} s[4];
int c = 0;
void dijkstra(int *a, int b[][4], int *d) {
int i = 0, j, min, t;
a[i] = 1; // 시작 노드 방문 표시
d[i] = 0; // 시작 노드까지의 거리는 0
s[i].from = 0;
// 시작 노드(0번)와 직접 연결된 노드의 초기 거리 설정
for (i = 0; i < 4; i++) {
if (b[0][i] == 0) {
continue;
} else {
d[i] = b[0][i];
s[i].from = 0;
}
}
while (c < 4) {
// 아직 방문하지 않은 노드 중 최소 거리 탐색
min = INFINITY;
for (i = 0; i < 4; i++) {
if (min <= d[i] || d[i] == 0 || a[i] == 1) {
continue;
} else if (min > d[i]) {
min = d[i];
}
}
// 최소 거리를 가진 노드의 인덱스 찾기
for (int k = 0; k < 4; k++) {
if (min == d[k]) {
t = k;
break;
} else {
continue;
}
}
a[t] = 1; // 선택한 노드 방문 처리
// 선택한 노드를 경유할 때 더 짧아지는 경로 갱신
for (j = 0; j < 4; j++) {
if (a[j] == 1 || b[t][j] == 0) {
continue;
} else if (a[j] != 1) {
if (d[j] > (d[t] + b[t][j])) {
d[j] = d[t] + b[t][j];
s[j].from = t;
}
}
}
c++;
}
// 결과 출력
for (int i = 0; i < 4; i++) {
cout << "경유 노드 " << s[i].from << ", 비용: " << d[i] << endl;
}
}
int main() {
int a[4]; // 방문 여부 배열
int d[4]; // 시작 노드로부터의 최단 거리 배열
for (int k = 0; k < 4; k++) {
d[k] = INFINITY; // 거리를 무한대로 초기화
}
for (int i = 0; i < 4; i++) {
a[i] = 0; // 모든 노드를 미방문 상태로 초기화
}
int b[4][4]; // 그래프의 인접 행렬
for (int i = 0; i < 4; i++) {
cout << (i + 1) << "번째 행의 값을 입력하세요:" << endl;
for (int j = 0; j < 4; j++) {
cin >> b[i][j];
}
}
dijkstra(a, b, d);
}
참고: 원본 코드의 사소한 문제 두 가지를 수정했습니다. 첫째, 함수 이름의 오타(djikstras → dijkstra)를 바로잡았습니다. 둘째, 거리를 갱신하는 부분의 s[i].from = t;를 s[j].from = t;로 고쳤습니다. 안쪽 루프가 끝난 시점의 i는 배열 범위를 벗어나므로, 갱신 대상 노드인 j를 사용해야 올바른 경유 노드가 기록됩니다.
실행 결과
1번째 행의 값을 입력하세요: 0 1 3 2 2번째 행의 값을 입력하세요: 2 1 3 0 3번째 행의 값을 입력하세요: 2 3 0 1 4번째 행의 값을 입력하세요: 1 3 2 0 경유 노드 0, 비용: 0 경유 노드 0, 비용: 1 경유 노드 0, 비용: 3 경유 노드 0, 비용: 2
코드 핵심 정리
- a[]: 각 노드의 방문 여부를 저장하는 배열입니다. 값이 1이면 해당 노드의 최단 거리가 확정되었다는 뜻입니다.
- d[]: 시작 노드(0번)로부터 각 노드까지의 현재 최단 거리를 저장하며, 처음에는 모두 무한대(INFINITY)로 초기화됩니다.
- b[][]: 그래프를 인접 행렬로 표현한 것으로, 값이 0이면 두 노드 사이에 간선이 없다는 의미입니다.
- s[].from: 해당 노드에 도달하기 직전에 거친 노드(경유 노드)를 기록하여, 나중에 실제 최단 경로를 역추적할 수 있게 해줍니다.
- 시간 복잡도: 매 반복마다 방문하지 않은 노드 전체를 선형 탐색하므로 이 구현의 시간 복잡도는 O(V²)입니다. 우선순위 큐를 사용하면 O((V+E) log V)로 개선할 수 있습니다.
다익스트라 알고리즘은 음수 가중치 간선이 없는 그래프에서 정확한 최단 경로를 보장합니다. DAG처럼 간선의 방향과 순서가 명확한 그래프에서는 위상 정렬 기반의 O(V+E) 풀이도 가능하지만, 일반적인 가중치 그래프에서는 위와 같은 다익스트라 구현이 널리 사용됩니다.