Shortest Path with Path

In this post, I would like to share knowledge about shortest path algorithm problem...
Usually this algorithm, only show how to return total distance of path that will been taken to reach the goal..
and below the sample code,

Graph.java

The sample output :

The shortest distance between 0 to 2 is 17.00

---

So, now I will show how to return list of path that been taken to reach the goal...
I will only explain two option to store the the list of path :

1. using Data Structure.
2. using Parent (Array).

Before that, because now we want to return two thing; distance and path; then..

Firstly we should split shortestPath() into three different function :

1. shortestPath() - to find shortest path from start point to all point
2. getShortestDistanceTo() - to obtain shortest distance from start point to goal
3. getPathTo() - to obtain all path that been taken to reach the goal

---

For the first option, I use LinkedList as storage and adding new line in shortestPath() function...

In updating distance part at line 80 to 87, there a line at line 85 that use to copy or clone the path list of minimum ID to update the path list of j. Then it will keep clone the the path until the path is the short one and need lot of memory if the number of node is bigger.

Below is the source code,

Graph.java

The sample output :

The shortest distance between 0 to 2 is 17.00
Path from 0 to 2 is -> 0 -> 1 -> 2

---

And this for the second option by using parent (array), it more simple and does not need to copy the path list every time the weight is update...
The thing that only need to update is it parent, the value of parent will initialize base on current minimum ID, if the weight is updated...
Then it use less memory that use data structure..but need a process when need return the path...
The path will obtain while the parent of root not equal to parent, and to store it still use Data Structure implementation.
And below the source code for this option,

Graph.java

The sample output :

The shortest distance between 0 to 2 is 17.00
Path from 0 to 2 is -> 0 -> 1 -> 2


At the end, this the only thing that i want to share in this post...
if I or the readers have any interest algorithm that U want me to post or discuss...
So, please email or comment on this post...
I will try to find the solution and share it for U..

you can test it by your self..

i hope you like this souce code...

and please give some comment....

                                                                                                                                                      Created By : Z-man, 2014