Shortest-Path Algorithms

---

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) to O(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