Dijkstra.java

import java.util.Scanner;

public class Dijkstra {
    private static final Integer INF = Integer.MAX_VALUE;
    private static final Integer[][] GRAPH = {
        { 0, 4, INF, 2, INF, INF },
        { 4, 0, 5, 1, INF, INF },
        { INF, 5, 0, 8, 2, 6 },
        { 2, 1, 8, 0, 10, INF },
        { INF, INF, 2, 10, 0, 3 },
        { INF, INF, 6, INF, 3, 0 }
    };
    private static final Integer[] TRAVELLED = new Integer[GRAPH.length];

    public static void main(String[] args) {
        Integer[][] distArray = new Integer[GRAPH.length][GRAPH.length];
        Integer[] distances = new Integer[GRAPH.length];
        Integer dist = 0;
        Integer vertex;
        Integer start;
        Integer end;
        Scanner s = new Scanner(System.in);
        
        System.out.print("Enter starting vertex: ");
        start = s.nextInt();
        vertex = start;
        
        System.out.print("Enter ending vertex: ");
        end = s.nextInt();
        
        for(Integer i=0; i<GRAPH.length; i++)
            for(Integer j=0; j<GRAPH.length; j++)
                distArray[i][j] = INF;
        
        for(int v=0; v<GRAPH.length && vertex!=end; v++){
            TRAVELLED[v] = vertex;
            for(int i=0; i<GRAPH.length; i++){
                if(!(GRAPH[vertex][i] == INF && GRAPH[i][vertex] == INF)) {
                    if(GRAPH[vertex][i]==INF){
                        distances[i] = dist + GRAPH[vertex][i];
                    } else {
                        distances[i] = (dist + GRAPH[vertex][i] < distArray[vertex][i]) ? dist + GRAPH[vertex][i] : distArray[vertex][i];
                    }
                } else {
                    distances[i] = distArray[vertex][i];
                }
            }
            for(int i=0; i<GRAPH.length; i++)
                distArray[vertex][i] = distances[i];
            vertex = getMin(distances, vertex);;
            dist = distances[vertex];
            if(v<GRAPH.length-1){
                System.out.println(vertex.toString() + ": " + distances[vertex].toString());
                for(int i=0; i<GRAPH.length; i++)
                    distArray[vertex][i] = distances[i];
            }
        }
    }
    
    private static Integer getMin(Integer[] arr, Integer vertex){
        Integer min = 0;
        for(Integer i=0; i<GRAPH.length; i++){
            if(!isTravelled(i))
                min=i;
        }
        for(Integer i=0; i<arr.length; i++){
            if(i!=vertex && !isTravelled(i)) 
                min = (arr[i] < arr[min]) ? i : min;
        }
        return min;
    }

    private static boolean isTravelled(Integer v) {
        for(int i=0; i<GRAPH.length; i++){
            if(TRAVELLED[i]==v)
                return true;
        }
        return false;
    }
}