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
