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

Question

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?

Answer 1

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])
                    previous[v] := u;
                    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

Answer 2

If you want a simpler answer and want to minimize space cost, you can simply add .00000001 (or some other extremely small fraction that is small enough that it will not significantly affect the weights of the paths and thus will not alter the overall result of running Dijkstra's) to every edge. This way, a path of size E = 5 and a path of size E = 10 that would otherwise be seen as equivalent in length under Dijkstra's can be differentiated due to the fact that the path of E = 10 will be 5 * whateverSmallFraction greater than the path of E = 5.

Answer 3

You can add a small value positive $\delta$ to each edge and use Dijkstra's algorithm to find the shortest path. Any $\delta < \frac{1}{V}$ will suffice.

Answer 4

The $\delta$ trick will work with a suitable choice of $\delta$, but a bulletproof method is to rate the paths with the pair (sum of weights, length), and use lexicographical ordering (i.e. in case of ties on the sums, compare the lengths).

Besides this, the algorithms remains completely unchanged.