Dijkstra’s Algorithm : Finding all possible shortest paths between two vertices in a graph 4

The following code implements the Dijkstra’s Shortest Path Algorithm and further extends is to get all possible shortest paths between two vertices.

For graph representation we make use of JUNG API, its usage, however, is primarily in visualizing the graph and can be extended easily for any other representation as well.

Random Graph Generator code is used to prepare some input graph for this code.

First, our code representation for the vertices in the graph:

Next, the algorithm implementation for finding the shortest paths:

Finally, some code to test the above implementation:

The input graph generator code can be obtained from here.

A sample output generated from the above code is shown below:

Red Color node is taken to be source node for calculating shortest paths to the rest of nodes.

Red Color node is taken to be source node for calculating shortest paths to the rest of nodes.

Output for this graph is as obtained below:

Dijkstra’s Algorithm : Finding all possible shortest paths between two vertices in a graph
4.5 (90%) 2 votes

4 thoughts on “Dijkstra’s Algorithm : Finding all possible shortest paths between two vertices in a graph

  1. Reply google plus android phone Aug 21,2014 3:00 pm

    Hey There. I found your blog using msn. That is a very neatly written article.
    I’ll be sure to bookmark it and come back to read more
    of your useful info. Thanks for the post. I will definitely comeback.

  2. Reply this is very useful to me Feb 12,2015 3:57 pm

    very useful

  3. Reply Tranthom Jan 17,2018 8:09 pm

    Could you give me this full code file, please?

    • Reply Anupam Jain Jan 17,2018 9:25 pm

      Hi,

      The code presented above is complete. You could simply copy-paste them and make java files as per class names. You should spend at least that much effort 😉

      -Thanks

Leave a Reply