/**
* @author shekhar
* @date 12/05/2010
* @description a function to print shortest path using dfs
**/
int min = MAX_VALUE; // sum of total distance
String finalP = ""; // store the shortest path
int vtex = NUMBER_VERTEX; // total number of vertex
boolean[] visited = new boolean[vtex]; // for cycle detection
int [][]graph;
void dfs (String path, int start, int destination, int distance){
if( start == destination){
if( min >= distance){
min = distance;
finalP = path;
}
return;
}
visited[start] = true;
for(int i = 0; i < vtex; i++ ){
if( visited[i] || graph[start][i] == 9999) // here 9999 is infinity/no-path
continue;
dfs(path +" > "+vertex[i], i,destination,distance + graph[start][i]);
}
visited[start] = false;
}

### Like this:

Like Loading...

*Related*

Man where is the details of the algorithm no example how can we understand..?????

Dear Santosh,

This is simple Depth First Search for weighted Graph and at the same time calculating the shortest path of given source and destination.

The above program is not advisable to use in real project as the complexity of the above algorithm is very high compare to Dijkstra and other known shortest path algorithms