We wil see a simple implementation of Dijkstra's algorithm to find the shortest path between two cities in a given graph.

Tasks:

• Try out the demo applet below to recap how shortest path works.


• The snippet of relevant code from CityGraph.java with today's tasks is listed below.
  
  
• Read through the snipppet and finish up the tasks within the given JAVA package to complete your shortest path program.

public class CityGraph {
    
    int num_cities;
    // The following 2D matrices store the graph adjacency and pairwise distance information.
    // Both the matrices are symmetric and of size num_cities x num_cities.
    boolean [][] adjacent_cities; // adjacent_cities[i][j] = true if city i is adjacent to city j
    float [][] pairwise_distance; // pairwise_distance[i][j] = infinity if city i is NOT adjacent to city j
    
    // Fields to keep track of the source to destination path information.
    int source_city, destination_city;
    int [] source_destination_path;
    float source_destination_distance;
    
    void getSourceDestinationShortestPath(){
        
        // visited array to keep track of cities to which we have computed the "shortest path" 
        // from source_city.
        // visited[i] = true if we have found the "shortest path" from source_city to city i.
        boolean [] visited = new boolean[num_cities]; // all cities are initialized as unvisited
        // only source_city is set as visited since we know it has distance 0.
        visited[source_city] = true;
        
        // shortest_distance array stores the shortest path distances to cities that have been visited.
        float [] shortest_distance = new float[num_cities];
        for( int i = 0; i < num_cities; i++ ) 
            shortest_distance[i] = Float.MAX_VALUE; // all city distances are initialized to infinity.
        // source_city has distance 0.
        shortest_distance[source_city] = 0;
         
        // previous_city is needed to backtrack the shortest path once we reach the destination_city
        // for instance, if we visit city 17 from city 5, we set previous_city[17] = 5. 
        int [] previous_city = new int[num_cities];
        // Since source_city is the first node, we initialize its previous node to -1.
        previous_city[source_city] = -1;
        
        // source_destination_distance is updated when we visit the destination_city
        source_destination_distance = Float.MAX_VALUE;
        
        // OUTER LOOP: loop until we visit the destination city
        while( !visited[destination_city] ){
 
            /* BRIEF IDEA:
             * In each iteration of OUTER loop we move exactly one city from the unvisited set 
             * to the visited set (i.e., we mark exactly one unvisited city as visited).
             * 
             * HOW TO CHOOSE WHICH CITY TO MARK AS VISITED?
             * Note that we have the shortest_distance array that stores the shortest distance values
             * to each of the VISITED cities from the source_city.
             * 
             * To find 'a' candidate UNVISITED city to mark as visited:
             *   (a) For each UNVISITED city: compute the best possible distance to source_city 
             *        using exactly "one hop" from a VISITED city.
             *   (b) The UNVISITED city with the smallest distance to source city in (a) above is the 
             *       city to mark as visited. 
             *   (c) The city which was one hop away from the candidate city is stored in the previous
             *       city array.     
             */
            
            /*  min_city is the candidate unvisited city  
             *  min_distance is the candidate distance for min_city
             *  prev_city_to_min_city is the VISITED city that is one hop away from min_city
             */
            int min_city = -1;
            float min_distance = Float.MAX_VALUE; // Set initially to infinity.
            int prev_city_to_min_city = -1;
            
            /* TASK:
             *   Complete the two for loops below to accomplish the following:
             *   For each UNVISITED city 'i'
             *       For each VISITED city 'j' that is ADJACENT to city 'i' 
             *      ( make use of adjacent_cities[][] matrix to check for adjacency )
             *      
             *           Find the distance from UNVISITED 'i' to source_city via the VISITED city 'j'.
             *            ( HINT: you need to use pairwise_distance[][] and shortest_distance[] )
             *            
             *          If the calculated new distance is less than min_distance
             *              (a) Update min_distance: what is the new min_distance?
             *              (b) Update min_city: what is the new min_city?
             *              (c) Update prev_city_to_min_city: what is the city previous to min_city?
             *          End If
             *              
             *       End for 'j'
             *    End for 'i'   
             */
            for( int i = 0; i < num_cities; i++ ){                
                
                for( int j = 0; j < num_cities; j++ ){
                    
                }
            }
            
            // If no min_city is found we cannot reach destination :(, hence break the OUTER loop.
            if( min_city < 0 ) break;  
            
            /* TASK:
             * Now update the three arrays below
             */
            // visited[????] = true;   // Which city is now newly VISITED?
            // shortest_distance[????] = ????; // What is the distance to the newly VISITED city?
            // previous_city[????] = ????; // Which city is previous to the newly VISITED city?
        }
        
        // No changes to code are needed after this.

http://cs-people.bu.edu/tvashwin/cs112_spring09/lab12.html