존슨 알고리즘

존슨 알고리즘: 음수 가중치 그래프에서의 최단 경로 탐색
그래프 이론은 다양한 현실 세계의 문제를 모델링하고 해결하는 강력한 도구
이 중에서도 "존슨 알고리즘"은 음수 가중치를 포함하는 그래프에서 모든 정점 쌍 간의 최단 경로를 찾는 문제를 효율적으로 해결
이 글에서는 존슨 알고리즘의 작동 방식과 활용 예시, 그리고 Python 코드를 통한 구현

Johnson's Algorithm 소개

Johnson's Algorithm은 다음과 같은 단계로 구성됩니다:

1. 추가 정점 추가 음수 가중치를 포함하는 그래프에 새로운 정점을 추가하고, 이 정점과 기존의 모든 정점 사이에 가중치가 0인 간선을 추가 → 음수 가중치에 대해 도움을 받을 수 있음
2. 벨만-포드 알고리즘 적용 추가한 정점에 대해서 벨만-포드 알고리즘을 실행하여 모든 정점 간의 최단 경로 추정값을 구함 벨만-포드 알고리즘은 음수 가중치를 처리할 수 있고, 음수 사이클이 있는지 검사할 수 있는 알고리즘
3. 간선 가중치 수정 원래 그래프의 간선 가중치를 수정하여 음수 가중치를 제거 이 때 음수 사이클이 없도록 조정
4. 다익스트라 알고리즘 적용 수정한 가중치를 기반으로 모든 정점 쌍 간의 최단 경로를 다익스트라 알고리즘을 사용하여 계산 다익스트라 알고리즘은 양수 가중치를 다루는데 효과적인 알고리즘

활용 예시

Johnson's Algorithm은 다양한 분야에서 활용됨
도로 네트워크에서 최단 경로를 계산
통신 네트워크에서 데이터 전송 시간을 최소화하기 위한 경로를 찾는 등의 문제에 적용
음수 가중치를 다루는 과제에서도 유용하게 활용

예시 코드

python

import sys

def bellman_ford(graph, source):
    distances = {node: float('inf') for node in graph}
    distances[source] = 0

    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if distances[node] + weight < distances[neighbor]:
                    distances[neighbor] = distances[node] + weight

    return distances

def johnsons_algorithm(graph):
    temp_node = "TEMP_NODE"
    graph[temp_node] = {node: 0 for node in graph}
    
    distances = bellman_ford(graph, temp_node)
    del graph[temp_node]
    
    modified_graph = {}
    for node in graph:
        modified_graph[node] = {}
        for neighbor, weight in graph[node].items():
            modified_graph[node][neighbor] = weight + distances[node] - distances[neighbor]
    
    all_pairs_shortest_paths = {}
    for node in modified_graph:
        all_pairs_shortest_paths[node] = dijkstra(modified_graph, node)
    
    for node in all_pairs_shortest_paths:
        for neighbor in all_pairs_shortest_paths[node]:
            all_pairs_shortest_paths[node][neighbor] += distances[neighbor] - distances[node]
    
    return all_pairs_shortest_paths

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    visited = set()
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        visited.add(current_node)

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 그래프 예시
graph = {
    'A': {'B': -2, 'C': 4},
    'B': {'C': 1, 'D': 7},
    'C': {'E': -3},
    'D': {'B': 3},
    'E': {'D': -2}
}

shortest_paths = johnsons_algorithm(graph)
print(shortest_paths)

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <climits>

using namespace std;

const int INF = INT_MAX;

void bellmanFord(const unordered_map<char, unordered_map<char, int>>& graph, const char& source, unordered_map<char, int>& distances) {
    distances[source] = 0;

    for (int i = 0; i < graph.size() - 1; ++i) {
        for (const auto& nodePair : graph) {
            char node = nodePair.first;
            for (const auto& neighborPair : graph.at(node)) {
                char neighbor = neighborPair.first;
                int weight = neighborPair.second;
                if (distances[node] != INF && distances[node] + weight < distances[neighbor]) {
                    distances[neighbor] = distances[node] + weight;
                }
            }
        }
    }
}

void dijkstra(const unordered_map<char, unordered_map<char, int>>& graph, const char& start, unordered_map<char, int>& distances) {
    priority_queue<pair<int, char>, vector<pair<int, char>>, greater<pair<int, char>>> pq;
    pq.push(make_pair(0, start));
    distances[start] = 0;

    while (!pq.empty()) {
        char current = pq.top().second;
        int currentDist = pq.top().first;
        pq.pop();

        if (currentDist > distances[current]) continue;

        for (const auto& neighborPair : graph.at(current)) {
            char neighbor = neighborPair.first;
            int weight = neighborPair.second;
            if (currentDist + weight < distances[neighbor]) {
                distances[neighbor] = currentDist + weight;
                pq.push(make_pair(distances[neighbor], neighbor));
            }
        }
    }
}

unordered_map<char, unordered_map<char, int>> modifyGraph(const unordered_map<char, unordered_map<char, int>>& originalGraph) {
    unordered_map<char, unordered_map<char, int>> modifiedGraph = originalGraph;

    // Add a temporary node and edges with weight 0 to all other nodes
    char tempNode = 'T';
    modifiedGraph[tempNode] = {};
    for (const auto& nodePair : originalGraph) {
        modifiedGraph[tempNode][nodePair.first] = 0;
    }

    return modifiedGraph;
}

unordered_map<char, unordered_map<char, int>> johnsonsAlgorithm(const unordered_map<char, unordered_map<char, int>>& graph) {
    unordered_map<char, int> distances;
    unordered_map<char, unordered_map<char, int>> modifiedGraph = modifyGraph(graph);
    bellmanFord(modifiedGraph, 'T', distances);
    modifiedGraph.erase('T');

    unordered_map<char, unordered_map<char, int>> adjustedGraph;
    for (const auto& nodePair : modifiedGraph) {
        char node = nodePair.first;
        adjustedGraph[node] = {};
        for (const auto& neighborPair : modifiedGraph.at(node)) {
            char neighbor = neighborPair.first;
            int weight = neighborPair.second;
            adjustedGraph[node][neighbor] = weight + distances[node] - distances[neighbor];
        }
    }

    unordered_map<char, unordered_map<char, int>> allPairsShortestPaths;
    for (const auto& nodePair : adjustedGraph) {
        char node = nodePair.first;
        unordered_map<char, int> shortestDistances;
        dijkstra(adjustedGraph, node, shortestDistances);
        allPairsShortestPaths[node] = shortestDistances;
    }

    for (auto& nodePair : allPairsShortestPaths) {
        char node = nodePair.first;
        for (auto& neighborPair : nodePair.second) {
            char neighbor = neighborPair.first;
            neighborPair.second += distances[neighbor] - distances[node];
        }
    }

    return allPairsShortestPaths;
}

int main() {
    unordered_map<char, unordered_map<char, int>> graph = {
        {'A', {{'B', -2}, {'C', 4}}},
        {'B', {{'C', 1}, {'D', 7}}},
        {'C', {{'E', -3}}},
        {'D', {{'B', 3}}},
        {'E', {{'D', -2}}}
    };

    unordered_map<char, unordered_map<char, int>> shortestPaths = johnsonsAlgorithm(graph);

    for (const auto& nodePair : shortestPaths) {
        char node = nodePair.first;
        cout << "Shortest paths from node " << node << ":\\n";
        for (const auto& neighborPair : nodePair.second) {
            char neighbor = neighborPair.first;
            int distance = neighborPair.second;
            cout << "To node " << neighbor << ": " << distance << endl;
        }
        cout << endl;
    }

    return 0;
}

존슨 알고리즘의 시간 복잡도

존슨 알고리즘은 벨만-포드 알고리즘과 다익스트라 알고리즘을 사용함으로써 시간 복잡도는 해당 알고리즘의 시간 복잡도에 영향을 받음
그래프의 정점 개수를 V, 간선 개수를 E라고 할 때,
벨만 - 포드 알고리즘의 시간 복잡도 : O(V*E)
다익스트라 알고리즘의 시간 복잡도 : O(V^2) 또는 O(E*log(V))
⇒ 존슨 알고리즘의 시간 복잡도는 주로 O(V * E + V^2) 또는 O(V * E * log(V))
벨만-포드 알고리즘의 실행 횟수가 다익스트라 알고리즘의 실행 시간에 비해 상대적으로 큰 영향을 미침 (음수 가중치가 들어있는 그래프에서 사용되는 알고리즘이므로)

결론

Johnson's Algorithm은 음수 가중치를 포함하는 그래프에서 최단 경로를 찾는 문제를 효율적으로 해결하기 위한 강력한 도구
이 알고리즘은 벨만-포드 알고리즘과 다익스트라 알고리즘을 결합하여 음수 가중치와 양수 가중치를 함께 다루는 방법을 제공
다양한 분야에서 실제 문제에 적용하여 해결하는 데 활용됨