Bellman-Ford
Problem: 求取单源最短路径，可判断有无负环
Complexity:
O(VE)Algorithm:
bool Bellman-Ford(G,w) {
// update at most G.V.num times
for i = 0 : G.V.num {
bool update = false;
for j = 0 : G.E.num -1 {
e(u,v) = G.E[j];
if (release(e(u, v))
update = true;
}
if (update == false)
return true; // no need to update again
if (i == G.V.num && update)
return false; // has negative circle
}
return false; //won't go here actually
}
Dijkstra
Problem: 求取单源最短路径，不能有负边
Complexity: varying from
O(V*V)toO(Vlog(V) + E)Algorithm :
Using array:
void Dijkstra_naive(G, w) { // Complexity O(V*V) while (true) {
minV = -1;
pick[0] = true;
for (i = 0 : G.V.num - 1) { // to get the nearest vertex
if (pick[i] == 0 && (minV == -1 || d[i] < d[minV])) {
minV = i;
}
}
if (minV == -1) return true; // no need to update again
pick[minV] = true;
for (i = 0 : G.V.num - 1) {
release(e(minV, i));
}
}
}
}
Using priority queue:
// totally V poll() and E add(), with complexity O(VlogV + ElogV)
public void Dijkastra_Priority_Queue(Vertex source) {
source.minDistance = 0.;
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<>();
vertexQueue.add(source);
while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll(); //O(log(V))
// Visit each edge exiting u
for (Edge e : u.adjacencies) {
Vertex v = e.target;
double weight = e.weight;
double distanceThroughU = u.minDistance + weight;
if (distanceThroughU < v.minDistance) {
vertexQueue.remove(v);
v.minDistance = distanceThroughU;
v.previous = u;
vertexQueue.add(v); //O(log(V))
}
}
}
}
Using Fibonacci heap:
public static void Dijkstra_Fibonacci_Heap(Node source) {
source.minDistance = 0.;
FibonacciHeap myHeap = new FibonacciHeap();
myHeap.insert(source, source.minDistance);
while (!myHeap.isEmpty()) {
Node u = myHeap.min(); //O(logV)
// Visit each edge exiting u
for (Edge e : u.adjacencies) {
Node v = e.target;
double weight = e.weight;
double distanceThroughU = u.minDistance + weight;
if (distanceThroughU < v.minDistance) {
v.minDistance = distanceThroughU;
myHeap.decreaseKey(v, v.minDistance); //O(1)
v.previous = u;
}
}
}
}
Aboving two versions from: Stackoverflow
Floyd
Problem: 多源无负权最短路径
Complexity: O(V^3)
Algorithm:
Floyd = function(G,w) {
for k = 0 : G.V.num - 1
for i = 0 : G.V.num - 1
for j = 0 : G.V.num - 1
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
SPFA
Problem: 单源最短路径，可含有负边
Complexity: O(kE) with k << E
Algorithm:
Using BFS:
void SPFA_bfs = function (G, s) {
queue<int> q;
q.push(s);
pick[s] = 1;
// if this while() loop executed too many times
// then the graph has negative edge
while (!q.empty) {
u = q.front();
q.pop();
for e(u,v) in G.V[u].edges {
if(release(e(u, v) && !pick[v]) {
pick[v] = true;
q.push(v);
}
}
}
}
Using DFS:
void SPFA_dfs = function (G, u) {
pick[u] = true; //pick is a global variable
for (e(u, v) in G.V.[u].edges) {
if (release(e(u,v)) && !pick[v]) {
if (SPFA_dfs(v)) return true; //no need to go on
}
else {
return true; //no need to go on
}
}
pick[u] = false; // this is important
return 0;
}
Discuss
Bellman-Ford is naive to checek release each edge for each iteration.
Dijkstra tries to release the edges of the nearest unpicked vertices only. So each time you need to get the nearset candidate. Using minHeap can reduce the complexity of getNearest() to 0(log(V)), but increase the inserting cost to 0(logV) (which is no need for Dijkstra_naive) Using FiboHeap use decreaseKey instead of insert(), with cost O(1) for each decreaseKey
SPFA use queue rather than heap to keep picked vertices. So adding or deleting vertices is simplfied to push() and pop() with complixity o(1). The main idea is that each vertex can be pushed into the queue only once.
Floyd is just dynamic programming
Reference
最短路（SPFA, Dijkstra, Floyd）: http://blog.csdn.net/lttree/article/details/27186637
带权重最短路: https://www.renfei.org/blog/weighted-shortest-path.html
Fibonacci Dijkstra:
http://stackoverflow.com/questions/15392289/java-using-a-fibonacci-heap-for-implementing-dijkstras-algorithm
SPFA: http://www.cnblogs.com/scau20110726/archive/2012/11/18/2776124.html
