존슨 알고리즘

존슨 알고리즘이란

존슨 알고리즘은 다익스트라의 효율성을 활용하지만 음수 가중치에 대하여도 올바른 결과를 생성할 수 있는 알고리즘입니다.
이를 해결하기 위해서는 벨만-포드 알고리즘을 활용해야 합니다.

1. 우선 더미 정점을 만든 후 모든 정점과 연결하고, 가중치를 0으로 초기화 합니다.
2. 그 후 0번 정점을 기준으로 벨만-포드 알고리즘을 작동하여 최단 거리를 측정합니다.
3. 시작 정점과 끝 정점 사이의 거리에 더미 정점부터 시작 정점까지의 거리는 더하고, 더미 정점부터 끝 정점까지는 빼줍니다.

벨만-포드 알고리즘을 통하여 반환되는 값은 distance[dummy, start]+weight(dummy, end)>=distance[dummy, end]의 조건을 항상 충족하기에 weight(dummy, end)+distance[dummy, start]-distance[dummy, end]의 값은 항상 0보다 크거나 같습니다.
즉 이 과정을 거치면 음수 가중치를 양수 가중치로 바꿀수 있습니다.

그래프

위의 그래프를 기준으로 양수 가중치를 구해보겠습니다.

1. 우선 각 정점의 최단 거리를 기록하겠습니다. 다음은 탐색순으로 정점을 나타내고 이의 최단거리를 기록한 것입니다.

0	1	2	0	3	4
0	-7	-9	0	-5	-1

2. 이제 기록된 정점간의 거리를 기록하겠습니다.

0-1	1-2	2-0	0-3	3-4
-7	-2	10	-5	4

3. 이제 주어진 식을 기준으로 계산해보겠습니다.()

(두 정점간의 가중치)=(두 정점간의 가중치)+(더미 정점부터 시작 정점간의 가중치)-(더미 정점부터 끝 정점간의 가중치)
(0부터 1(-7))+(S부터 0(0))-(S부터 1(-7))=0
-7+0-(-7)=0
(1부터 2(-2))+(S부터 1(-7))-(S부터 2(-9))=0
-2+-7-(-9)=0
(2부터 0(10))+(S부터 2(-9))-(S부터 0(0))=1
10+(-9)-(0)=1
(0부터 3(-5))+(S부터 0(0))-(S부터 3(-5))=0
-5+0-(-5)=0
(3부터 4(4))+(S부터 3(-5))-(S부터 4(-1))=0
-4+(-5)-(-1)=0

추가로 0부터 4까지의 가중치부분은 책에 나와있지 않으나 구해보자면 (0부터 4(2))+(S부터 0(0))-(S부터 4(-1))=3
2+0-(-1)=3

이를 토대로 양수 가중치를 구하였고 이는 다음과 같습니다.

0-1	1-2	2-0	0-3	3-4	0-4
0	0	1	0	0	3

양수 가중치

양수 가중치를 다시 음수 가중치로 만들기 위해서는 위에서 빼주었던 더미 정점부터 도착 정점까지의 거리를 다시 더해주면 됩니다.

존슨 알고리즘의 구현

#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;
 
    for(int i=0; i<V; i++)
    {
        for(auto& e : edges)
        {
            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);
}

그래프

실행 결과