C++로 구현하는 Johnson 알고리즘 – 그래프 최단 경로 찾기

이 글에서는 그래프 이론에서 두 정점 사이의 최단 경로를 구하는 Johnson 알고리즘에 대해 살펴보겠습니다.

아래와 같은 그래프가 주어지면, 각 정점 쌍 사이의 최단 경로 거리를 계산할 수 있습니다. 이 프로그램은 정점의 개수, 간선의 개수, 그리고 각 간선과 그 비용을 입력으로 받아 모든 정점 간 최단 거리를 담은 거리 행렬을 출력합니다.

입력 예시

• 정점: 3개
• 간선: 5개
• 간선 비용:

1 2 8
2 1 12
1 3 22
3 1 6
2 3 4

출력 결과

계산된 그래프의 거리 행렬은 다음과 같습니다.

예를 들어, 정점 1에서 정점 3으로 직접 이동하는 비용은 22이지만, 정점 2를 경유하면 8 + 4 = 12라는 훨씬 낮은 비용으로 도달할 수 있습니다. 이처럼 알고리즘은 가능한 모든 경로를 고려하여 최솟값을 찾아냅니다.

알고리즘 동작 원리

johnsonAlgorithm(cost)

입력: 주어진 그래프의 비용(가중치) 행렬

출력: 임의의 정점에서 다른 모든 정점까지의 최단 경로가 담긴 행렬

Begin
    비용 행렬과 동일한 새 행렬 'A'를 생성한다.
    i번째 행과 j번째 열 사이에 간선이 없으면 A[i, j]에 무한대(INF)를 넣는다.
    for k := 1 to n do
        for i := 1 to n do
            for j := 1 to n do
                A[i, j] = min(A[i, j], A[i, k] + A[k, j])
            done
        done
    done
    현재 A 행렬을 출력한다.
End

핵심은 세 번 중첩된 반복문입니다. 정점 k를 거쳐가는 경로(i → k → j)가 기존의 직접 경로(i → j)보다 짧다면 값을 갱신하는 방식으로, 모든 정점 쌍에 대한 최단 거리를 점진적으로 완성해 나갑니다. 이 과정을 경로 완화(relaxation)라고 부르며, 전체 시간 복잡도는 O(n³)입니다.

C++ 구현 예제

#include<iostream>
#define INF 9999
using namespace std;
int min(int a, int b);
int cost[10][10], adj[10][10];
inline int min(int a, int b){
    return (a<b)?a:b;
}
main() {
    int vert, edge, i, j, k, c;
    cout << "Enter no of vertices: ";
    cin >> vert;
    cout << "Enter no of edges: ";
    cin >> edge;
    cout << "Enter the EDGE Costs:\n";
    for (k = 1; k <= edge; k++) { // 입력받은 간선 정보를 adj, cost 행렬에 저장
        cin >> i >> j >> c;
        adj[i][j] = cost[i][j] = c;
    }
    for (i = 1; i <= vert; i++)
        for (j = 1; j <= vert; j++) {
            if (adj[i][j] == 0 && i != j)
                adj[i][j] = INF; // 간선이 없으면 무한대로 설정
        }
    for (k = 1; k <= vert; k++)
        for (i = 1; i <= vert; i++)
            for (j = 1; j <= vert; j++)
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]); // k를 경유하는 i→j 경로 중 최솟값으로 갱신
    cout << "Resultant adj matrix\n";
    for (i = 1; i <= vert; i++) {
        for (j = 1; j <= vert; j++) {
            if (adj[i][j] != INF)
                cout << adj[i][j] << " ";
        }
        cout << "\n";
    }
}

실행 결과

Enter no of vertices: 3
Enter no of edges: 5
Enter the EDGE Costs:
1 2 8
2 1 12
1 3 22
3 1 6
2 3 4
Resultant adj matrix
0 8 12
10 0 4
6 14 0

실행 결과를 보면 대각선 요소는 자기 자신으로의 거리이므로 0이며, 나머지 요소에는 각 정점 쌍 사이의 최단 거리가 기록되어 있습니다. 간선이 존재하지 않거나 도달할 수 없는 경우에는 무한대 값(INF)이 유지되므로, 실제 응용에서는 이를 별도로 처리해 주는 것이 좋습니다.