COP 3530
SECTIONs U02, U03
SPRING 2014


                     THE SHORTEST PATH ALGORITHM
                     ===========================



I. The Program:

/**
 *
 * @author pelina
 */
public class Main {
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // print title
        System.out.println("TESTING THE SHORTEST PATHS ALGORITHM");
        System.out.println("====================================\n\n\n");
        
        // define a cost matrix
        int[][] c = { {0, 10, 20, 10, INFINITY, INFINITY}, 
           {INFINITY, 0, INFINITY, INFINITY,INFINITY, 25} ,
           {35, INFINITY, 0, 45, 40, 15}, 
           {INFINITY, INFINITY, INFINITY,0, INFINITY, 25},
           {INFINITY, 15, 30, 45, 0, INFINITY}, 
           {INFINITY,25,INFINITY,40, INFINITY, 0}};
        
        printCostMatrix(c);
        int[] d = shortestPaths(4,c);
        System.out.println("\nThe shortest paths from 4 to the other vertices is: ");
        for (int i = 0; i < 6; i++)
            if ( d[i] < INFINITY)
                System.out.println("d[4," + i + "] = " + d[i]);
            else
                System.out.println("d[4," + i + "] = INFINITY");
        
        System.out.println("\nThe shortest paths from 5 to the other vertices is: ");
        d = shortestPaths(5,c);
        for (int i = 0; i < 6; i++)
            if ( d[i] < INFINITY)
                System.out.println("d[5," + i + "] = " + d[i]);
            else
                System.out.println("d[5," + i + "] = INFINITY");
        
    }
    
    // cost is an n X n matrix of non-negative integers
    // cost[i][j] is the cost of the arc from i to j
    // if there is no arc, the cost is INFINITY
    // it returns the cost of the minimal path from
    // the vertex v to the vertices of the graph
    public static int[] shortestPaths( int v, int[][] cost)
    {
        // get the set of vertices
        int n = cost.length;
        // declare the arrays dist and s
        // dist[i] is the distance from v to i
        // s[i] is true if there is a path from v to i
        int[] dist = new int[n];
        boolean[] s = new boolean[n];
        
        // initialialize dist
        for (int i = 0; i < n; i++)
            dist[i] = cost[v][i];
        s[v] = true;
        
        // determine n-1 paths from v 
        for ( int j = 2 ; j < n  ; j++ )
        {
            // choose u such that dist[u] is minimal for all w with s[w] = false
            // and dist[u] < INFINITY
            int u = -1;
            for (int k = 0; k < n; k++)
                if ( !s[k] && dist[k] < INFINITY)
                    // check if u needs updating
                    if ( u < 0 || dist[k] < dist[u])
                        u = k;
            if (u < 0)
                break; // 
            // set s[u] to true and update the distances
            s[u]=true;
            for (int k = 0; k < n; k++)
                if ( !s[k] && cost[u][k] < INFINITY )
                    if( dist[k] > dist[u] + cost[u][k])
                        dist[k] = dist[u] + cost[u][k];
            // at this point dist[k] is the smallest cost path from
            // v to k of length j.
        }     
            
        return dist;
        
    }
    
    // print the cost matrix
    public static void printCostMatrix(int[][] c)
    {
        System.out.printf("The cost matrix c[i,j]\n");
        System.out.printf(" i/ j");
        // print header
        for (int i = 0; i < c.length; i++)
            System.out.printf("%6d", i);
        // print the matrix
        for (int i = 0; i < c.length; i++)
        {
            System.out.printf("\n%2d   ", i);
            for (int j = 0 ; j < c.length; j++)
                if ( c[i][j] == INFINITY)
                    System.out.printf("%6s", "INF");
                else
                    System.out.printf("%6d", c[i][j]);
        }
    }    
    
    private static final int INFINITY = Integer.MAX_VALUE;
}


II. The output:

run:
TESTING THE SHORTEST PATHS ALGORITHM
====================================



The cost matrix c[i,j]
 i/ j     0     1     2     3     4     5
 0        0    10    20    10   INF   INF
 1      INF     0   INF   INF   INF    25
 2       35   INF     0    45    40    15
 3      INF   INF   INF     0   INF    25
 4      INF    15    30    45     0   INF
 5      INF    25   INF    40   INF     0
The shortest paths from 4 to the other vertices is: 
d[4,0] = 65
d[4,1] = 15
d[4,2] = 30
d[4,3] = 45
d[4,4] = 0
d[4,5] = 40

The shortest paths from 5 to the other vertices is: 
d[5,0] = INFINITY
d[5,1] = 25
d[5,2] = INFINITY
d[5,3] = 40
d[5,4] = INFINITY
d[5,5] = 0
BUILD SUCCESSFUL (total time: 1 second)