2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ What have you tried, to answer your own question? Have you tried running your candidate algorithm on a few small graphs? Have you tried to prove it correct (e.g., via a modification of the standard proof of correctness for Dijkstra's algorithm)? $\endgroup$
    – D.W.
    Dec 2, 2013 at 4:29

4 Answers 4

3
$\begingroup$

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
$\endgroup$
11
  • $\begingroup$ Would appreciate if you could add some more pseudocode. I also need to have 2 lists right? With visited and unvisited vertexes? $\endgroup$ Dec 2, 2013 at 1:13
  • $\begingroup$ I have modified my answer to include a full algorithm. I simply took what Wikipedia offered and modified some parts. You can see what parts are added because they don't have a line number. In particular, the most important part is after the (annotated) line 17. $\endgroup$ Dec 2, 2013 at 1:28
  • $\begingroup$ Don't forget to select this answer (or another answer if any) if you feel it's good so the question won't remain open. $\endgroup$ Dec 2, 2013 at 1:30
  • $\begingroup$ What's the reason for the weird addition of previous[v] := u; if !visited[v] insert v into Q; end if which is absent in the original code ? $\endgroup$ 21 hours ago
  • $\begingroup$ How do you choose vertex in Q with smallest distance in case of ties ? $\endgroup$ 21 hours ago
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Welcome to the site! It's probably worth noting here that the small fraction you add needs to be smaller than the smallest edge weight divided by $n$, so that the "extra" weight of a path never exceeds the length of a real edge. But it also needs to be big enough that you don't get loss of significance while calculating path lengths. $\endgroup$ May 12, 2017 at 8:26
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This works when minimum edge-weight of graph is 1. $\endgroup$ Jun 2, 2020 at 16:45
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.