## Modified Dijkstra

Modify Dijkstra algorithm such that if there is more than one shortest path between node u and v ,dijkstra would select the shortest path with minimum nodes. For example if we can reach from u to v in cost S in two different path ( for example u-p-q-r-v and u-a-v both with same cost S) then our modified algorithm should select path u-a-v because it has minimum path weight as well as minimum node in between u and v.

Solution:

We would only modify the RELAX(u,v,w) function in the original Dijkstra algorithm.

Here nc[V] means the smallest count of nodes between source (S) and corresponding node (V). We will initialize nc[s] = 0 for the algorithm.

Modified_relax(u,v,w)

if d[v] < d[u] + w(u,v) {

d[v] = d[u] + w(u,v)

nc[v] = nc[u] + 1

}

else if ( d[v] == d[u] + w(u,v) )

if ( nc[v] < nc[u] + 1 ) { // nc means node count

nc[v] = nc[u] + 1;

}