Shorstest Path Problem Categories:

1. From a speicific start point;
2. To a specific end point;
3. Start and end with a specific point;
4. Search for all the shortest path in every pair nodes.

Dijkstra:

This algorithm is aiming at caculating all the shortest paths from every point to a specific start point. And it’s a greedy algorithm.

Algorithm:

1. Set the distance to the start node as infinity to all the nodes except the start node.
2. Initial a set which conclude the added nodes, and another set for unvisited nodes.
3. For the added nodes set, we find the shortest edge from adjancent nodes crossing this set in unvisited set. And add the adjancent node to the added added nodes.
4. Update the distances of nodes from start node which connect to the last added node.
5. Do step 3 and 4 repeatedly until all the nodes are in the added set.

Pseudoode:

function Dijkstra(Graph, source):

    create vertex set Q

    for each vertex v in Graph:             // Initialization
    dist[v] ← INFINITY                  // Unknown distance from source to v
    prev[v] ← UNDEFINED                 // Previous node in optimal path from source
    add v to Q                          // All nodes initially in Q (unvisited nodes)

    dist[source] ← 0                        // Distance from source to source

    while Q is not empty:
        u ← vertex in Q with min dist[u]    // Source node will be selected first
        remove u from Q 

        for each neighbor v of u:           // where v is still in Q.
            alt ← dist[u] + length(u, v)
            if alt < dist[v]:               // A shorter path to v has been found
                dist[v] ← alt 
                prev[v] ← u 

    return dist[], prev[]

Java Code:

public static void dijkstra(int[][] edges, int s, int[] dist, int[] pre) {
    int n = edges.length;

    HashSet<Integer> set = new HashSet<Integer>(n);

    for (int i = 0; i < n; i++) {
        dist[i] = Integer.MAX_VALUE;
        set.add(i);
    }
    dist[s] = 0;

    while (!set.isEmpty()) {
        int min = findMin(set, dist);
        for (int i = 0; i < n; i++) {
            if (edges[min][i] != -1) { // find the neighbors of the node
                if (dist[i] < dist[min] + edges[min][i]) { //relaxation
                    dist[i] = dist[min] + edges[min][i];
                    pre[i] = min;
                }
            }
        }
    }
}
private static int findMin(Set set, int[] dist) {
    int min = Integer.MAX_VALUE, minIdx = -1;
    for (int i = 0; i < dist.length; i++) {
        if (set.contains(i) && dist[i] < min) {
            min = dist[i];
            minIdx = i;
        }
    }
    set.remove(minIdx);
    return minIdx;
}

Running Time:

O(E*lgv)

If use the Fibonacci heap -> O(V*lgV + E)

Bellman Ford:

Aimming at searching for the shortest path from a specific start node. It is useful also for the graph containing the negative edges. It’s a dynamic programming algorithm.

Algorithm: