존슨 알고리즘(Johnson's Algorithm)

존슨 알고리즘(Johnson's Algorithm)

• 벨만-포드 알고리즘 과 다익스트라 알고리즘 의 방법을 결합하여 모든 정점 사이의 최단 경로를 구하는 알고리즘
• 다익스트라 알고리즘의 효율성을 활용함과 동시에 음수 가중치를 갖는 그래프에 대해서도 올바른 결과를 생성할 수 있음.
• 상당히 새로운 접근 방법을 사용함.
  • 음수 가중치에 대한 다익스트라 알고리즘의 한계를 극복하기 위해 전체 에지 가중치를 음수가 아닌 형태로 변환 함.
    • 벨만-포드 알고리즘 과 적절한 수학 논리 를 결합하여 이루어짐.

 

동작 방식

• 그래프에 새로운 더미(Dummy) 정점 을 추가함.
  • 그리고 이 더미 정점과 나머지 모든 정점 사이에 가중치가 0인 에지를 연결함.
• 이후 벨만-포드 알고리즘 을 이용하여 더미 정점과 나머지 정점들 사이의 최단 경로를 찾고, 나중에 사용하기 위해 각 정점까지의 최단 거리를 기록함.

더미 정점 추가

• 더미 정점과 나머지 모든 정점 사이에 가중치가 0인 에지를 연결했기 때문에 모든 최단 거리 값은 0보다 클 수는 없음.
• 또한 그래프의 모든 정점에 대한 연결을 통해 거리 값이 모든 가능한 순회 경로에서 일정한 관계를 유지할 수 있음.
  • 에지 가중치와 최단 거리의 합 연산이 간단해질 수 있음.
    • 이동 경로상의 연속한 정점에 대해서 거리 값 연산이 서로 상쇄되어, 결국 전체 합 은 첫 번째 정점과 마지막 정점의 거리 값 차 와 같음.

예 : 음수 가중치가 있는 그래프

• A부터 E까지의 정점이 있는 그래프에 더미 정점 S를 추가한 형태
• 설명
  • 검은색 에지 옆 괄호 안에 적힌 숫자 : 에지 가중치
  • 정점 아래 빨간색 글자 : S에서 각 정점까지의 최단 경로와 최단 거리
  • 빨간색 실선 화살표 : S로부터 출발하는 최단 경로
  • 점선 화살표 : 최단 경로에서 사용되지 않은 가중치가 0인 에지

 

• 그래프를 A -> B -> C -> A -> D -> E 순서로 탐색할 경우, 각 정점의 최단 거리

• 각 정점의 거리 사이에 초기 에지 가중치를 추가하면 다음과 같음.

• 각 에지 가중치에 다음 수식을 적용함.
  • w(uv) : 정점 u와 v 사이의 초기 에지 가중치
  • d[s, u] : s 정점과 u 정점 사이의 최단 경로 거리
  • d[s, v] : s 정점과 v 정점 사이의 최단 경로 거리
  • W(uv) : 변환된 에지 가중치
• W(uv) = w(uv) + d[s, u] - d[s, v]
• 위 수식을 실제로 적용한 결과는 다음과 같음.

AB -> (-7) + 0 - '(-7)' = 0
BC -> (-2) + '(-7)' - '(-9)' = 0
CA -> 10 + '(-9)' - '0' = 1
AD -> (-5) + '0' - '(-5)' = 0
DE -> 4 + '(-5)' - (-1) = 0

• 위 수식을 연속적으로 적용할 경우, 각 줄의 세 번째 항 은 다음 줄의 가운데 항 에 의해 상쇄되는 것을 발견할 수 있음.
  • 이를 망원(Telescoping) 속성이라고 함.
    • 수학 용어 중 망원 급수(Telescoping Series) 와 관련된 단어
    • 길이 조절이 되는 옛날 망원경처럼 덧셈항과 뺄셈항이 서로 상쇄되어 수식이 짧아진다는 의미
• 이 속성으로 인해 A 정점에서 E 정점까지의 최소 거리를 나타내는 다음 두 수식은 완전히 같음.
  • (w(AB) + d[s, A] - d[s, B]) + (w(BC) + d[s, B] - d[s, C]) + ... + (w(DE) + d[s, D] - d[s, E])
  • (w(AB) + w(BC) + w(CA) + w(AD) + w(DE)) + d[s, A] - d[s, E]
• 즉, 두 정점 사이를 연결하는 경로에 더해지는 값은 어느 경로를 선택하든 항상 같음.
• 벨만-포드 알고리즘 이 반환하는 거리 배열 d에 대해, 항상 d[s, u] + weight(u, v) >= d[s, v] 조건을 만족하기 때문에 변환된 가중치는 음수가 될 수 없음.
  • w(u, v) + d[s, u] - d[s, v] 값은 무조건 0보다 같거나 큰 수임.
• 이러한 가중치 변환 수식을 이용하면, 그래프에서 모든 최단 경로상에 존재하는 에지의 가중치가 0으로 변경됨.
  • 원래의 최단 경로 순서는 그대로 유지한 채, 음이 아닌 가중치로 구성된 그래프가 만들어짐.
• 이제 새로운 가중치를 갖는 그래프의 각 정점에서 다익스트라 알고리즘 을 적용하여 모든 정점 쌍 사이의 최단 거리를 구할 수 있음.

 

코드

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct Edge {
    int src;
    int dst;
    int weight;
};

const int UNKNOWN = INT_MAX;

bool HasNegativeCycle(const vector<Edge>& edges, vector<int> distance) {
    for (auto& e : edges) {
        if (distance[e.src] == UNKNOWN) {
            continue;
        }

        if (distance[e.src] + e.weight < distance[e.dst]) {
            return true;
        }
    }

    return false;
}

vector<int> BellmanFord(vector<Edge> edges, int V) {
    vector<int> distance(V + 1, UNKNOWN);

    int s = V;
    for (int i = 0; i < V; i++) {
        edges.push_back(Edge {s, i, 0});
    }

    distance[s] = 0;

    // 정점 개수가 V + 1개이므로 V번 반복
    for (int i = 0; i < V; i++) {
        for(auto& e : edges) {
            // 에지의 시작 정점의 거리 값이 UNKNOWN이면 스킵
            if (distance[e.src] == UNKNOWN) {
                continue;
            }

            // 인접한 정점의 거리 값이 새로운 경로에 의한 거리 값보다 크면
            // 거리 값을 업데이트함.
            if (distance[e.dst] > distance[e.src] + e.weight) {
                distance[e.dst] = distance[e.src] + e.weight;
            }
        }
    }

    // 음수 가중치 사이클이 있는지 검사
    if (HasNegativeCycle(edges, distance)) {
        cout << "음수 가중치 사이클 발견!" << endl;
        return {};
    }

    return distance;
}

int GetMinDistance(vector<int>& distance, vector<bool>& visited) {
    int minDistance = UNKNOWN;
    int minIndex = -1;

    for (int i = 0; i < distance.size(); i++) {
        if (!visited[i] && distance[i] <= minDistance) {
            minDistance = distance[i];
            minIndex = i;
        }
    }

    return minIndex;
}

vector<int> Dijkstra(vector<Edge> edges, int V, int start) {
    vector<int> distance(V, UNKNOWN);
    vector<bool> visited(V, false);

    distance[start] = 0;

    for (int i = 0; i < V - 1; i++) {
        // 방문하지 않은 정점 중에서 최소 거리 정점을 찾음.
        int curr = GetMinDistance(distance, visited);

        visited[curr] = true;

        for (auto& e : edges) {
            // 인접한 정점만 고려
            if (e.src != curr) {
                continue;
            }

            // 이미 방문했으면 무시
            if (visited[e.dst]) {
                continue;
            }

            if (distance[curr] != UNKNOWN && distance[e.dst] > distance[curr] + e.weight) {
                distance[e.dst] = distance[curr] + e.weight;
            }
        }
    }

    return distance;
}

void Johnson(vector<Edge> edges, int V) {
    // 더미 정점을 추가한 그래프에서 최단 거리를 계산
    vector<int> h = BellmanFord(edges, V);

    if (h.empty()) {
        return;
    }

    // 에지 가중치 재설정
    for (auto& e : edges) {
        e.weight += (h[e.src] - h[e.dst]);
    }

    // 모든 정점들 사이의 최단 거리를 저장
    vector<vector<int>> shortest(V);

    for (int i = 0; i < V; i++) {
        shortest[i] = Dijkstra(edges, V, i);
    }

    // 가중치 변환 수식을 역으로 적용하여 최단 거리를 출력
    for (int i = 0; i < V; i++) {
        cout << i << ":\n";

        for (int j = 0; j < V; j++) {
            if (shortest[i][j] != UNKNOWN) {
                shortest[i][j] += h[j] - h[i];

                cout << "\t" << j << ": " << shortest[i][j] << endl;
            }
        }
    }
}

int main() {
    int V = 5;              // 정점 개수
    vector<Edge> edges;     // 에지 포인터의 벡터

    vector<vector<int>> edge_map {  // {시작 정점, 목표 정점, 가중치}
        {0, 1, -7},
        {1, 2, -2},
        {2, 0, 10},
        {0, 3, -5},
        {0, 4, 2},
        {3, 4, 4}
    };

    for (auto& e : edge_map) {
        edges.emplace_back(Edge {e[0], e[1], e[2]});
    }

    Johnson(edges, V);

    return 0;
}

 

결과

0:
        0: 0 
        1: -7
        2: -9
        3: -5
        4: -1
1:
        0: 8 
        1: 0 
        2: -2
        3: 3 
        4: 7
2:
        0: 10
        1: 3
        2: 0
        3: 5
        4: 9
3:
        3: 0
        4: 4
4:
        4: 0