Modifying Dijkstra’s algorithm to favor the path with least amount of edges

Problem Detail: 

I need to modify the Dijkstra's algorithm to get the shortest path in a directed graph and get the one with the least amount of edges if there are equal paths.

I am thinking to add another data field to count the number of edges from start and compare them in same way as weights. Would that work?

Asked By : user2067051

Answered By : bourbaki4481472

Yes, it should. You can simply keep a count of edges traveled. If you discover a new shortest path which is of the same distance as the last shortest path, make an if statement asking whether or not the new path has less number of edges. Here is a short pseudo code that you can use in the "relaxation" part of algorithm.

if (new_path == shortest_path && new_path_edges < shortest_path_edges)     shortest_path= new_path elseif (new_path < shortest_path)     //The relaxation part of Dijkstra's algorithm 

EDIT. Fuller answer below.

 1  function Dijkstra(Graph, source):  2      for each vertex v in Graph:  3          dist[v]      := infinity;             dist_edges[v]:= 0;  4          visited[v]   := false;  5          previous[v]  := undefined;  6      end for  7        8      dist[source]  := 0;         dist_edges[source] := 0;  9      insert source into Q; 10                                                                 11      while Q is not empty: 12          u := vertex in Q with smallest distance in dist[] and has not been visited; 13          remove u from Q; 14          visited[u] := true 15           16          for each neighbor v of u:    17              alt := dist[u] + dist_between(u, v);                 alt_edges := dist_edges[u] + 1; //Note the increment by 1                 if (alt = dist[v] && alt_edges < dist_edges[v])                     dist[v]= alt                     dist_edges[v]= alt_edges 18              if alt < dist[v]:                                  19                  dist[v]  := alt;                     dist_edges[v] := alt_edges;                 20                  previous[v]  := u; 21                  if !visited[v]: 22                       insert v into Q; 23                  end if 24              end if 25          end for 26      end while 27      return dist; 28  endfunction 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18515