HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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?

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.

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

Code 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 algorithm
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

Context

StackExchange Computer Science Q#18515, answer score: 4

Revisions (0)

No revisions yet.