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;
}

Create a free website or blog at WordPress.com.

%d bloggers like this: