djakstralinkstate

import java.util.*;

public class djakstralinkstate {
    public int distance[] = new int[10];
    public int cost[][] = new int[10][10];

    public void calc(int n, int s) {
        int flag[] = new int[n + 1];
        int i, minpos = 1, k, c, minimum;
        for (i = 1; i <= n; i++) {
            flag[i] = 0;
            this.distance[i] = this.cost[s][i];
        }
        c = 2;
        while (c <= n) {
            minimum = 99;
            for (k = 1; k <= n; k++) {
                if (this.distance[k] < minimum && flag[k] != 1) {
                    minimum = this.distance[i];
                    minpos = k;
                }
            }
            flag[minpos] = 1;
            c++;
            for (k = 1; k <= n; k++) {
                if (this.distance[minpos] + this.cost[minpos][k] < this.distance[k] && flag[k] != 1)
                    this.distance[k] = this.distance[minpos] + this.cost[minpos][k];
            }
        }
    }

    public static void main(String args[]) {
        int nodes, source, i, j;
        Scanner in = new Scanner(System.in);
        System.out.println("Enter the Number of Nodes \n");
        nodes = in.nextInt();
        djakstralinkstate d = new djakstralinkstate();
        System.out.println("Enter the Cost Matrix Weights: \n");
        for (i = 1; i <= nodes; i++)
            for (j = 1; j <= nodes; j++) {
                d.cost[i][j] = in.nextInt();
                if (d.cost[i][j] == 0)
                    d.cost[i][j] = 999;
            }
        System.out.println("Enter the Source Vertex :\n");
        source = in.nextInt();
        d.calc(nodes, source);
        System.out.println("The Shortest Path from Source\t" + source + "\t to all other vertices are : \n");
        for (i = 1; i <= nodes; i++)
            if (i != source)
                System.out.println(
                        "source :" + source + "\tdestination :" + i + "\t MinCost is :" + d.distance[i] + "\t");
    }
}
/*
 * OUTPUT
 * iotlab@iotlab-Veriton-M200-B360:~$ javac Dijkstra.java
 * iotlab@iotlab-Veriton-M200-B360:~$ java Dijkstra
 * Enter the Number of Nodes
 * 5
 * Enter the Cost Matrix Weights:
 * 0 1 0 2 0
 * 1 0 1 0 4
 * 0 1 0 0 3
 * 2 0 0 0 3
 * 0 4 3 3 0
 * Enter the Source Vertex :
 * 1
 * The Shortest Path from Source 1 to all other vertices are :
 * source :1 destination :2 MinCost is :1
 * source :1 destination :3 MinCost is :2
 * source :1 destination :4 MinCost is :2
 * source :1 destination :5 MinCost is :5
 */