1
$\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?

|cite|improve this question
$\endgroup$
  • $\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 '13 at 4:29
2
$\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
|cite|improve this answer
$\endgroup$
  • $\begingroup$ Would appreciate if you could add some more pseudocode. I also need to have 2 lists right? With visited and unvisited vertexes? $\endgroup$ – user2067051 Dec 2 '13 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$ – bourbaki4481472 Dec 2 '13 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$ – bourbaki4481472 Dec 2 '13 at 1:30
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.

|cite|improve this answer
$\endgroup$
  • 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$ – David Richerby May 12 '17 at 8:26

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.