양수 가중치를 가지는 그래프에서 O(V+cE)로 최단경로 구하기

가중치가 없는, 혹은 모든 간선의 가중치가 1인 그래프에서는 BFS를 이용하면 $O(V+E)$로 최단경로를 구할 수 있다. 이를 응용하여, 가중치가 $c$ 이하의 자연수인 그래프에서 최단경로를 구하자.

가중치 $c$의 간선을, 가중치 $1$의 간선 $c$개로 나누자. 그러면 새로운 노드가 $c-1$개가 생길 것이다. 그러고 나면 간선이 $O(cE)$개, 정점이 $O(V+cE)$개인 그래프가 된다. 여기서 BFS를 통해 최단경로를 구하면 $O(V+cE)$로 최단경로를 구할 수 있다. 이 방법은  $c$가 작을 때 유용하다.

https://www.geeksforgeeks.org/shortest-path-weighted-graph-weight-edge-1-2/ 참고.

 

내 코드

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100010;
const int MAXM = 100010;
const int MAXC = 10;
const int MAXNN = MAXN + MAXM * MAXC;

int N, M, S, E;
int U[MAXM], V[MAXM], C[MAXM];
vector<int> ed[MAXNN];
int NN;
int dis[MAXNN];

void addedge(int x, int y) {
	ed[x].push_back(y);
	ed[y].push_back(x);
}

int bfs() {
	NN = N;						// 새로 만들어진 노드를 포함한 노드의 개수
	for(int i = 0; i < M; i++) {
		if(C[i] == 1) addedge(U[i], V[i]);
		else {
			addedge(U[i], ++NN);
			for(int j = 0; j < C[i] - 2; j++, NN++)
            			addedge(NN, NN + 1);	// 노드를 새로 만들며 연결
			addedge(NN, V[i]);
		}
	}

	memset(dis, -1, sizeof(dis));
	queue<int> q;
	q.push(S);
	dis[S] = 0;
	while(!q.empty()) {				// BFS
		int t = q.front();
		q.pop();
		for(auto a : ed[t]) if(dis[a] == -1) {
			dis[a] = dis[t] + 1;
			q.push(a);
		}
	}
	return dis[E];
}