생뚱맞게 갑자기 Johnson's all-pairs shortest path 튜토리얼을 올려본다. 실은 지난 주에 수업하다가 존슨 알고리즘 얘기를 했는데, 방향 그래프에 대해서만 동작한다는 것을 망각하고 예제를 들었다가 헷갈렸기 때문에... 애들한테 나중에 블로그에 올려주겠다고 했다.
덕분에, 왠만하면 빠질 줄 알았던 이 알고리즘도 원고에 들어갈 듯 -_ -;;;
1 도입
1.1 최단거리 알고리즘의 소개
주어진 그래프 위에서 두 정점간을 잇는 경로 중 가중치의 합이 가장 작은 경로를 찾는 최단 거리 문제 (shortest path problem) 은 그래프에 관련된 문제 중 가장 유명하고 유용한 것이다. 흔히 사용되는 '고전' 최단거리 알고리즘들은 몇 가지 분류로 나뉘는데, 그 중 가장 유명한 것이 다음 세 가지인 것 같다.
- Dijkstra's shortest path algorithm
- Bellman-Ford shortest path algorithm
- Floyd-Warshall shortest path algorithm
이 세 가지는 각각 다른 동작 특성을 가진다. 앞의 두 개는 시작점 하나가 주어질 때, 시작점으로부터 다른 모든 정점까지의 최단거리를 찾아 준다는 의미에서, 단일 시작점 최단 경로 알고리즘이라고 부르고, Floyd-Warshall 알고리즘은 모든 시작점과 끝점 쌍에 대한 최단 거리를 찾아 준다.
각각의 시간 복잡도는 다음과 같다: 는 정점의 수,
는 간선의 수라고 둘 때,
- Dijkstra:
- Bellman-Ford:
- Floyd-Warshall:
1.2 음수 가중치의 중요성
위의 목록을 보면, 같은 역할을 하는 Bellman-Ford 알고리즘보다 Dijkstra 알고리즘의 시간 복잡도가 작은 것을 볼 수 있다. 그렇다면 Bellman-Ford 알고리즘은 애초에 왜 사용되는 것일까?
그래프로 표현하고자 하는 문제의 종류에 따라 그래프들은 음수 가중치를 가질 수 있다. 그런데 Dijkstra 의 최단거리 알고리즘은 그 정당성을 증명하는 과정에서 음수 가중치를 가질 수 없다는 가정을 써먹기 때문에, 음수 가중치를 갖는 그래프에 대해서는 사용될 수 없다. 따라서, 음수 가중치가 있는 그래프에 대해서는 대개 Bellman-Ford 알고리즘을, 음수 가중치가 없을 경우에는 대개 Dijkstra 알고리즘을 사용하게 된다.
하나 유의할 점은, 음수 가중치가 있는 무방향 그래프에 대해서는 음수 합을 갖는 사이클이 없다고 하더라도 최단 거리 문제가 정의되지 않는다는 것이다. 대부분의 알고리즘은 무방향 그래프를 양방향으로 간선 하나씩을 갖는 방향 그래프로 취급하는데, 음수 가중치를 갖는 무방향 간선은 이 방법에서 음수 합을 갖는 사이클로 변환되기 때문이다. 따라서, 이하에서 다루는 음수 가중치를 갖는 그래프들은 모두 방향 그래프라고 가정한다.
1.3 희소 그래프에 대한 모든 쌍 최단거리 알고리즘
모든 쌍의 최단거리를 찾아 주는 Floyd-Warshall 알고리즘은 그 간단한 구현 때문에 많은 사람들이 좋아하는 알고리즘 중 하나이다. 하지만, 이 알고리즘은 입력이 항상 연결 행렬로 주어진다고 가정하며, 간선의 수가 정점의 수에 비해 현저히 적은 경우에도 여전히 의 시간을 유지한다는 부담이 있다. (이와 같은 그래프를 희소sparse 그래프라고 하며, 반대의 경우를 밀집dense 그래프라고 한다)
(그림) 희소 그래프와 밀집 그래프의 예
따라서, 이런 그래프에 대해서는 모든 시작점에 대해 Dijkstra 의 최단거리 알고리즘을 번 반복적으로 적용해 모든 쌍의 최단거리를 찾겠다는 생각을 할 수 있다. 이 경우 전체의 시간 복잡도가
가 되기 때문에,
인 경우 현저한 속도 향상을 얻을 수 있게 된다.
그러나, 그래프에 음수 간선이 있는 경우에는 어떻게 될까? 물론 우리는 모든 정점에서 의 Bellman-Ford 알고리즘을 사용할 수 있다: 그러나, 이 방법의 시간 복잡도는
이므로, 최선의 경우에도 Floyd-Warshall 의 최단 거리 알고리즘보다 나을 게 없다.
이 때 등장하는 것이 바로 Johnson 의 최단 거리 알고리즘이다. 이 알고리즘은 가중치 재명명 (relabeling) 이라는 흥미로운 기법을 이용해, 그래프의 간단한 변형으로 어떻게 그래프의 음수 가중치를 모두 없앨 수 있는지를 보여준다. 변형한 그래프는 기존 그래프에서의 최단 경로를 그대로 보존하므로, 이 방법을 통해 원 그래프에서의 최단 경로를 찾을 수 있다는 것 또한 보인다.
이와 같은 기법은, 최소 비용 최대 유량 (min-cost max-flow) 문제를 푸는 방법 중 하나인 successive shortest path algorithm 에서도 유용하게 사용된다.
2 가중치 보정 (relabeling)
2.1 최단거리의 속성
그래프 위에서 한 시작 정점 를 정하고,
부터 다른 모든 정점까지의 최단 거리를 구하자. 그런데, 위 그림과 같이, 30 의 가중치를 갖는 간선
로 연결된 두 정점에 대해
까지의 최단거리가 10,
까지의 최단거리가 50 인 상황이 발생할 수 있을까? 물론 없다.
까지의 최단 경로의 끝에
를 이으면 길이 40 인 경로를 얻을 수 있기 때문이다.
이와 같은 속성을 정확하게 쓰면 다음과 같다. 까지의 최단거리를
라고 두면,
에 대해 다음이 성립한다:
- 모든 간선
에 대해
, 이 때
는 해당 간선의 가중치
생각해 보면 이 속성은 매우 자연스럽다는 것을 알 수 있다. Johnson 의 최단거리 알고리즘은 가중치 보정을 위해 바로 이 속성을 이용한다.
2.2 가중치의 보정과 최단 거리의 유지
이와 같은 값을 어디에다 쓸 수 있단 말인가? 위에서 얘기한 속성
이 도움이 된다. 위 부등식에서 를 우변으로 옮기면,
을 얻을 수 있다. 이 때 이 좌변의 값을 보정된 가중치 로 잡자. 그러면, 이 보정된 가중치는 항상 음수가 아니라는 것을 알 수 있다.
위 그래프는 이와 같은 보정을 거친 그래프 를 보여준다. 이 그래프에선 더 이상 음수 간선이 없다는 것을 확인할 수 있다.
물론, 단순히 음수 간선을 없애는 것은 모든 간선의 가중치의 절대값을 취해 주는 것만으로도 충분하다. 우리가 이 변형을 사용하는 이유는 이 변형한 그래프에서 두 정점 사이의 최단 경로가 원래 그래프에서의 최단 경로와 동일하기 때문이다. 이것 또한 쉽게 증명할 수 있다.
임의의 정점 와
를 잇는 두 경로
와
를 생각하자. 이 때, 변형된 그래프에서 각 경로의 길이는 각각
의 길이 =
의 길이 =
가 된다. 이 때, 를
와
로 풀어 보면:
다. 과
등이 한 번씩 더해지고 빠지는 것을 보면, 결국 다음과 같이 정리할 수 있다:
그러면, 변경된 그래프에서 두 경로의 길이는 정확하게 원래 그래프에서의 길이에 를 더한 것이 된다. 모든 경로의 길이에 똑같은 값을 더하기 때문에, 변경된 그래프에서의 최단 경로는 원래 그래프에서도 최단 경로가 된다.
2.3 그래프의 변형과 Bellman-Ford 알고리즘
Johnson 의 최단 거리 알고리즘은, 그래프 가 주어질 때, 그래프의 모든 정점과 연결되는 슈퍼소스 (supersource) 정점
를 추가한다. 이 때,
는 모든 정점으로 나가는 단방향 간선이 있으며, 모든 간선의 가중치는 0 이다.
위 그림들이 이 과정을 보여준다. 오른쪽 그림은 왼쪽 그림의 주어진 그래프에 를 추가한 그래프이다. (점선으로 표시된 간선들이 새로 추가된 간선들이다)
Johnson 의 최단 거리 알고리즘은 이와 같은 변형 과정을 거친 그래프에서, 를 시작점으로 하는 Bellman-Ford 알고리즘을 수행해 다른 모든 정점까지의 최단 거리를 구한다 - 이 최단 거리를
라고 하자. 아래 그림은 각 정점별로 계산된
값을 보여준다.
그러면,
에 따라, 다음과 같이 새로운 가중치들을 갖는 그래프 를 얻을 수 있다.
<img style="text_formatted" src="http://jmk.pe.kr/upload/get/156/4" title="가중치가 보정된 그래프 G'}
이 때, 이 그래프에서의 모든 간선은 음수가 아니므로, Dijkstra 알고리즘을 사용해 간단히 모든 쌍의 최단 거리를 구할 수 있게 된다.
2.4 구현
다음은 Bellman-Ford, Dijkstra, Johnson 의 최단거리 알고리즘을 구현하는 방향 그래프 클래스의 구현이다. 설명은 위에 다 있으니 자세한 설명은 생략한다... :-)
lang:cpp
const int INF = 987654321;
struct DiGraph {
struct Edge {
int target, weight;
Edge(int t, int w) : target(t), weight(w) { }
};
vector<vector<Edge> > adj;
int getV() const { return adj.size(); }
DiGraph(int V) {
adj.resize(V);
}
int addVertex() {
adj.push_back(vector<Edge>());
return adj.size()-1;
}
void addEdge(int a, int b, int c) {
adj[a].push_back(Edge(b, c));
}
bool bellmanFord(int start, vector<int>& ret) const {
int V = getV();
ret.resize(V);
fill(ret.begin(), ret.end(), INF);
ret[start] = 0;
int lastRelaxed = -1;
for(int round = 0; round < V; ++round)
for(int here = 0; here < V; ++here)
for(int i = 0; i < adj[here].size(); ++i) {
int there = adj[here][i].target;
int cost = adj[here][i].weight;
if(ret[there] > ret[here] + cost) {
lastRelaxed = round;
ret[there] = ret[here] + cost;
}
}
return lastRelaxed < V-1;
}
void dijkstra(int start, vector<int>& ret) const {
int V = getV();
ret.resize(V);
fill(ret.begin(), ret.end(), INF);
priority_queue<pair<int, int> > pq;
ret[start] = 0;
pq.push(make_pair(0, start));
while(!pq.empty()) {
int cost = -pq.top().first;
int here = pq.top().second;
pq.pop();
if(ret[here] < cost) continue;
for(int i = 0; i < adj[here].size(); ++i) {
int there = adj[here][i].target;
int thereCost = cost + adj[here][i].weight;
if(ret[there] > thereCost) {
ret[there] = thereCost;
pq.push(make_pair(-thereCost, there));
}
}
}
}
bool johnson(vector<vector<int> >& ret) {
ret.clear();
int V = getV();
int superSource = addVertex();
for(int i = 0; i < V; ++i)
addEdge(superSource, i, 0);
vector<int> h;
if(!bellmanFord(superSource, h)) return false;
V = getV();
for(int here = 0; here < V; ++here)
for(int i = 0; i < adj[here].size(); ++i) {
int there = adj[here][i].target;
adj[here][i].weight += h[here] - h[there];
}
ret.resize(V-1); // exclude super-source
for(int start = 0; start < V-1; ++start) {
dijkstra(start, ret[start]);
ret[start].pop_back(); // distance to super-source must be zero
for(int end = 0; end < V-1; ++end)
if(ret[start][end] != INF)
ret[start][end] -= h[start] - h[end];
}
return true;
}
"/> ;
