Shortest PATH [using DFS]


/**
* @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;
}
Advertisements

2 thoughts on “Shortest PATH [using DFS]

    • 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: