Dijkstra's algorithm to find all the shortest paths possible

Question

Hello, 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.If anyone have an ideea and can help me,i would really appreciate it.A link would be fine too.

Thank you.

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" );
        }
}

Answer 1

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 depth changes.

Answer 2

I'll give you a hint, but I feel like this is homework and I don't want to solve it for you.

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. That might be a good place to insert some additional logic.

Good luck.

Answer 3

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

Answer 4

I have fixed it,it's a kind of un-orthodox method,but at least it works... I took all the possible routes,removed duplicated solutions,remove the solutions with the cost higher than min,and that's about it.Thank you for your help.

Answer 5

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.