Shortest path between two nodes in a graph (Java)

Question

I have a program with a graph whose nodes represent some processes, and the proccess computing time is the node's cost.This graph is maintainded in memory as a list of nodes and each nod has a list of parent and children, and his execution time.

I must find the path with the minimum execution time.

• Each node can connect with any other.
• There is only one start node and one end node.
• One node can have various "parent" and "children"

Can someone tell me the best way to do this?

Solution 1

You can use Dijkstra's Algorithm for this.

Solution 2

Dijkstra has been mentioned already, there is also the A* algorithm which can be better performance-wise under certain conditions and from which one can learn a lot. There is also a good book on graph algorithms with lots of Java code examples by Robert Sedgewick which I found useful several years ago. The title is "Algorithms in Java, Part 5: Graph Algorithms".

Solution 3

One way to do this is by using various shortest path algorithm, such as Dijkstra's algorithm. For this to work, you would need to code a 'heap', a data structure in which the node with the smallest weight-age is on the top.

The idea behind the algorithm is to keep track of the overall distance from the start to the current node for the current route. The usual greedy algorithm is one where you just select the neighbouring node with the shortest path. Dijkstra expands on this by picking the node which would give the shortest overall distance from the start node to that node.

Solution 4

JGraph has an implementation of the Dijkstra algorithm.

Solution 5

Some notes specificly on Dijkstra algorithm in Java:

http://renaud.waldura.com/doc/java/dijkstra/

And a note about performance:

The complexity of Dijkstra's algorithm depends heavily on the complexity of the priority queue Q. If this queue is implemented naively as I first introduced it (i.e. it is re-ordered at every iteration to find the mininum node), the algorithm performs in O(n2), where n is the number of nodes in the graph.

With a real priority queue kept ordered at all times, as we implemented it, the complexity averages O(n log m). The logarithm function stems from the collections PriorityQueue class, a heap implementation which performs in log(m). With a real priority queue kept ordered at all times, as we implemented it, the complexity averages O(n log m).

View more solutions