patternMinor
Modifying Dijkstra’s algorithm to favor the path with least amount of edges
Viewed 0 times
paththedijkstraedgeswithfavoramountalgorithmleastmodifying
Problem
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?
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?
Solution
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.
EDIT. Fuller answer below.
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 algorithmEDIT. 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 endfunctionCode Snippets
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 algorithm1 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 endfunctionContext
StackExchange Computer Science Q#18515, answer score: 4
Revisions (0)
No revisions yet.