Shortest Path Problem - YashasKamath/IECSE-Summer-Bootcamp-2022 GitHub Wiki

Dijkstra's algorithm is an algorithm to find the shortest paths between two nodes in a graph. For a given source node, this algorithm finds the minimum distance between the source node and every other node in the graph.

Let the source node be named the root. Let the distance of the node Y be the distance from the root to the node Y. The algorithm advances as follows,

1. Mark all the nodes as unvisited. Create a set of vertices with all the vertices as unvisited set.

2. Initialize the distance values for every node to infinity except for the root node which is set to zero.

3. For the current node, consider all it's neighbours and change the values of the distance to the minimum between the current value and the distance through the current node. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B through A will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value.

4. When the iteration is completed, mark this current node as visited and remove it from the unvisited set. This ensures that a visited node will never be visited again.

5. Move to the next node in the unvisited set with minimum distance value and repeat the above steps for this node.

6. If the node selected is already visited or if all the unvisited nodes have the distance value as infinity, then stop. The algorithm is finished.

The pseudocode for the algorithm is,

Algorithm Dijkstra(Graph,Source):
    create vertex set Q
    for each vertex V in Graph: 
        dist[V] <- inf
        prev[V] <- undefined
        add V to Q
    dist[source] <- 0
    while Q is not empty do
        u <- vertex in Q with minimum dist[u]
        remove u from Q
        for each neighbour v in u do
            alt <- dist[u] + weight(u,v)
            if alt < dist[v] then
                dist[v] <- alt
                prev[v] <- u
    return dist[],prev[]   

The following gif shows how the algorithm works.

The time complexity of this algorithm is O(E + V log V).