Home > Uncategorized > Modified Dijkstra

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;

}

Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: