CODEWITHSUNDEEP
graphdijkstra
Darksody
Darksody

Reputation: 379

Dijkstra's algorithm to find all the shortest paths possible

I'm working on Dijkstra's algorithm, and I really need to find all the possible shortest paths, not just one. I'm using an adjacency matrix and I applied Dijkstra's algorithm, and I can find the shortest path. But I need to find all the paths with that minimum cost, I mean all the possible solutions, if they exist.

This is how my algorithm works, for a single solution:

public void dijkstra( int graph[][] )
{
    int d[] = new int[ graph.length ];
    int dC[] = new int[ graph.length ];
    int p[] = new int[ graph.length ];

    for( int i = 0; i < graph.length; i++ ){
        d[ i ] = 100; dC[ i ] = 100; p[ i ] = -1;
    }
    d[ 0 ] = 0; dC[ 0 ] = 0;

    int i = 0, min = 200, pos = 0; //You can change the min to 1000 to make it the largest number
    while( i < graph.length ){
        //extract minimum
        for( int j = 0; j < dC.length; j++ ){
            if( min > d[ j ] && dC[ j ] != -1 ){
                min = d[ j ]; pos = j;
            }
        }
        dC[ pos ] = -1;

        //relax
        for( int j = 0; j < graph.length; j++ ){
            if( d[ j ] > graph[ pos ][ j ] + d[ pos ] ){
                d[ j ] = graph[ pos ][ j ] + d[ pos ];
                p[ j ] = pos;
            }
        }
        i++; min = 200;
    }

    for( int j = 0; j < p.length; j++ ){
        System.out.print( p[ j ] + " " );
    }
    System.out.print( "\n" );
    for( int j = 0; j < d.length; j++ ){
        System.out.print( d[ j ] + " " );
    }
    System.out.print( "\n" );
}

Upvotes: 23

Views: 49382

Answers (8)

szabozoltan
szabozoltan

Reputation: 736

Consider this algorithm: https://www.programmingalgorithms.com/algorithm/dijkstra's-algorithm/php/ At the end there is a "< $distance[$v])" condition. If we change it to "<= ...", it will give all the existing shortest paths.

For collecting the paths we can put a

$this->paths[$v][] = $u; row here also. The whole snippet is here: https://pastebin.com/gk2ymyWw

                if (!$this->known[$v] && $graph[$u][$v] && $this->distance[$u] != $this->INT_MAX && $this->distance[$u] + $graph[$u][$v] <= $this->distance[$v]) {
                    $this->distance[$v] = $this->distance[$u] + $graph[$u][$v];
                    $this->paths[$v][] = $u;
                }

Upvotes: 1

ConcernedOfTunbridgeWells
ConcernedOfTunbridgeWells

Reputation: 66612

If your implementation of Dijkstra's algorithm is based on a priority queue, take your first solution, record the depth and keep popping solutions out until the distance changes.

Upvotes: 5

user7497021
user7497021

Reputation: 25

I Just solved a task to find all possible shortest paths on leetcode.com using Dijkstra's algorithm.

The only difference is how you extract information from "parents" and "distances" arrays.

The main idea is

  • you are moving from target to source and from each node in your optimal path ("parents" array),
  • you are looking for neighbors who had same minimal distances to the source like recorded parent, and
  • then recursively moving through all of those possible parents till you reach the source.

Below is the code in Python.

if parent[endNode] > -1: # -1 means no path at all
            self.traversingAllNodes(parents, shortestDistances, endNode, [endNode])
    return self.finalList

def traversingAllNodes(self, parents, distances, startNode, path):
    if parents[startNode] == -1:
        self.saveFound(path) # saving one path
        return
    currentNode = startNode
    parent = parents[currentNode] # recorded parent
    optimalDistance = distances[parent] # distance from parent to source
    for node in self.graph[currentNode]: # moving via neighbords
        if distances[node] == optimalDistance: 
            path.append(node)
            self.traversingAllNodes(parents, distances, node, path)
            path.remove(node)

Upvotes: 0

Memin
Memin

Reputation: 4090

FloydWarshallShortestPaths class of JgraphT finds all shortest paths. Based on above comments, you are looking for shortest paths between two vertices. You may want to use getShortestPaths method, which will return all shortest paths from the a vertex to all other vertices. Then you may want to filter the result which interests you.

Upvotes: 1

mtsr
mtsr

Reputation: 3142

This paper from 1982 describes an algorithm for graphs with multi-dimensional edge weights, that gives all shortest paths.

The algorithm works fine with simple weighted graphs, so should work for your case.

The author compares it to Dijkstra, both in how it works and in a run-time complexity comparison.

In pseudocode, paraphrasing the paper:

1. H is a heap of paths sorted on the weights of these paths, either
     a. lexicographically and decreasing in each element of the weight vector
     b. on the negative sum of all the elements in the weight vector
   Initially, H contains only path p0 (the starting point) the weight of which is O.
2. S1 through Sv are sets associated with vertices v1 through vv respectively.
   These sets contain the maximal paths to each vertex, as they are discovered.
   Initially, all sets are empty.
3. a. While (H is not empty) do begin
   b.   remove the root of H, p;
   c.   if p is not dominated by any of the paths in Sn where vn is last vertex of p
   d.     add it to Sn (the set of maxima for vertex vn)
   e.     for each possible extensions q of path p
   g.       if path q to node vm is not yet dominated by the maxima in Sm
   h.         insert q into H

Upvotes: 0

Anderson Imes
Anderson Imes

Reputation: 25650

If you look at Dijkstra's algorithm in pseudocode form here: Wikipedia Dijkstra's Algorithm Pseudocode

You will notice the line referred to as a Relax. Right now it only contains a case for if the path found is less than the current shortest path, but there isn't anything done if they are equal. You should probably keep all the equally short paths in a List.

Upvotes: 20

Dimitris Andreou
Dimitris Andreou

Reputation: 8898

If your graphs allows edges with weight = 0 and also allows cycles, bear in mind that there are infinitely many shortest paths, and you cannot hope to output them all!

If there are either no zero-weight edges, or your graph is a DAG, then your solution is still problematic: it either doesn't produce all shortest paths as required, or it does so withO(2^N) space and time complexity. But then, perhaps there might be as many shortest paths, so you can not hope to do better in the general case.

This is the best source for a slightly more general problem: Finding the k Shortest Paths (Eppstein). You could apply this by iterating the shortest paths, stopping at the first path that is longer than the previous.

For the restricted problem of finding only the (equivalent) shortest paths, Anderson Imes' hint above (is this homework? Otherwise someone should spell it out) is good and much simpler than the above.

Upvotes: 4

fortran
fortran

Reputation: 76057

I'm not very sure Dijkstra's algorithm can be easily adapted to do that; of course is not as simple as removing the visited edges, because the n shortest might share some of them.

So an almost brute force, but heuristically oriented solution, is to try this:

  • for every edge E in the shortest path:
    • remove E and run the modified Dijkstra again over the new graph
    • if the shortest path is longer than the first one obtained, stop
    • else, repeat recursively removing one edge at a time from the new sub-graph

My intuition tells me that it should work, with an increase in complexity proportional to the length (n in number of edges) of the first solution... If there are no more shortest path, it should end in the first round, if it founds another, it goes on with n-1 tries. The worst case complexity increase estimation over the original algorithm is very bad (n! I guess?), but that also means that there are lots of paths, so that is a work that needs to be done with any algorithm...

edit: Thinking a little bit more, the complexity increase might be even larger than the factorial of the number of nodes of the first found path, as the second might have even more nodes! So I think it's very difficult to estimate the complexity of this method, but it should be something like the number of valid solutions times the average number of nodes in the paths times the number of nodes squared (this last term being the original complexity of the unmodified algorithm).

edit 2: I've found a research paper about this subject, it requires subscription to get the full text but maybe you can find it somewhere else: http://ieeexplore.ieee.org/Xplore/login.jsp?reload=true&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F7719%2F21161%2F00982778.pdf%3Farnumber%3D982778&authDecision=-201

Upvotes: 1

Related Questions