Dijkstra's algorithm

Dijkstra's algorithm:

Dijkstra's algorithm for shortest path can be used to find the shortest path from the source vertex to any one vertex or all of the vertices of the graph. It is a good example for dynamic programming where the shortest path from source vertex to the optimized vertices (not in unoptimized set Q) is calculated and the process continues till all vertices are optimized (or target vertex is optimized).

Below is the pseudocode for Dijkstra's algorithm from wiki. min[] (minimum distance from source to optimized vertices) and previous[] (previous vertex with minimum distance) are maintained. Initially all vertices are in Q, min[source] is 0 and other min values are infinity, previous[] for all vertices is undefined. A vertex x in Q with smallest min[] is chosen by using priority queue or heap (with log|V| time). For all neighbors n of x where n in Q, we update the existing min distance to n (min[n]) if we can get to n through x with smaller distance (min[x] + dist_between(x, n)) and also previous[n] as x.

function Dijkstra(Graph, source):
    for each vertex v in Graph:
        min[v] = infinity
        previous[v] = undefined
    min[source] = 0
    
    Q = the set of all nodes in Graph // unoptimized nodes in Q
    while Q is not empty:
        x = node in Q with smallest min[x]
        remove x from Q
        for each neighbor n of x and n not removed from Q:
            min_x_n = min[x] + dist_between(x, n)
            if min_x_n < min[n]:
                min[n] = min_x_n
                previous[n] = x
    
    return previous[]

If we know the target vertex, we can break out of the while loop when target is the node removed from Q with smallest min (at the start of the while loop). If we exhaust all the nodes (till Q is empty), then we get the minimum distance for all the nodes from source.


Dijkstra's algorithm with limit:

Another variation of the problem is to enforce a limit or range value. Then we maintain another array left[] for each vertex to specify the value remaining so far after that vertex is traversed (left[n] = limit - min[n] or left[n] = left[x] - dist_between(x, n)). We initialize it to 0 for all vertices and left[source] = limit. We check if left[x] - dist_between(x, n) >= 0 before updating the min[n] and previous[n] and also update left[n] i.e. we only update distance or costs if they are within the limit or range. If limit if greater than the shortest paths to targets, the process is the same. If limit if lesser, then we get an x with min[x] = infinity and quit the process with no path. 

function Dijkstra(Graph, source, limit):
    for each vertex v in Graph:
        min[v] = infinity
        previous[v] = undefined
    min[source] = 0
    
    Q = set of all nodes in Graph // unoptimized nodes
    while Q is not empty:
        x = node in Q with smallest min[]
        if x == undefined: // all min[x] is infinity
            return null // no path exists
        remove x from Q
        for each neighbor n of x and n not removed from Q:
            min_x_n = min[x] + dist_between(x, n)
            if min_x_n < min[n] && min_x_n <= limit:
                min[n] = min_x_n
                previous[n] = x
    
    return previous[]

This behaves similar to the A* algorithm where left[x] acts as the heuristic_cost(x) function and min[x] as the actual_cost(x) function. The difference in A* and Dijkstra with limit is that - heuristic_cost(x) is an estimated function, instead of limit - min[x] and x picked from Q is the node with smallest heuristic_cost(x) + actual_cost(x), instead of smallest actual_cost(x). Thus, the original Dijkstra's algorithm without the limit is a special case of A* algorithm where the heuristic_cost(x) is 0.

By enforcing a limit, all the vertices of the graph are not explored. This is particularly useful when there are a lot of vertices in the graph (ex: maps).

If we use a binary heap for extracting the minimum node from Q, then I think the algorithm takes O(|E|+|V|log |V|) (O((|E|+|V|) log |V|) according to wiki). It takes O(|V|) for while loop, O(log|V|) for extracting smallest min from binary heap and only O(|E|) for the for each loop.