Shortest Path Faster Algorithm

The Shortest Path Faster Algorithm (SPFA) is a single-source shortest paths algorithm.

It is similar to Dijkstra's algorithm in that it performs relaxations on nodes popped from some sort of queue, but, unlike Dijkstra's, it is usable on graphs containing edges of negative weight, like the Bellman-Ford algorithm. Its value lies in the fact that, in the average case, it is likely to outperform Bellman-Ford (although not Dijkstra's). In theory, this should lead to an improved version of Johnson's algorithm as well.

The algorithm works by repeatedly selecting a vertex and using it to relax, if possible, all of its neighbors. If a node was successfully relaxed, then it might in turn be necessary to use it to relax other vertices, and hence it is marked for consideration also. Once there are no vertices left to be considered, the algorithm terminates. Note that a vertex might be considered several times during the course of the algorithm. The usual implementation strategy is to use a queue to hold the vertices that might be considered next.

int spfa(int s, int t) {
	for (int i = 1; i <= n; i++) d[i] = 1e9, vis[i] = 0;
	d[s] = 0; vis[s] = 1;
	queue <int> Q;
	Q.push(s);
	while (!Q.empty()) {
		int x = Q.front(); Q.pop();
		vis[x] = 0;
		for (auto &l : v[x]) {
			int y = e[l].b;
			if (d[y] > d[x] + e[l].c) {
				d[y] = d[x] + e[l].c;
				p[y] = l;
				if (!vis[y]) {
					vis[y] = 1;
					Q.push(y);
				}
			}
		}
	}
	return d[t];
}

'Problem Solving > Algorithm' 카테고리의 다른 글

Parametric Search (파라메트릭 서치)  (2)	2017.02.14
Minimum Spanning Tree(최소 스패닝 트리)  (0)	2017.02.07
Divide & Conquer Optimization in DP  (3)	2016.06.12
Lowest Common Ancestor(최소 공통 조상)  (0)	2016.03.31
Smallest Enclosing Circle/Sphere Problem  (0)	2016.02.17