Dijkstra Algorithm

import java.util.Scanner;

public class Dijkstra {
private int D[];
private int num_ver;
public static final int MAX_VALUE = 999;

public Dijkstra(int n) {
this.num_ver = n;
D = new int[n + 1];
}

public void shortest(int s, int A[][]) {
boolean visited[] = new boolean[num_ver + 1];

for (int i = 1; i <= num_ver; i++) {
D[i] = MAX_VALUE;
visited[i] = false;
}

D[s] = 0;

for (int count = 1; count <= num_ver – 1; count++) {
int u = -1;
for (int v = 1; v <= num_ver; v++) {
if (!visited[v] && (u == -1 || D[v] < D[u])) {
u = v;
}
}

visited[u] = true;

for (int v = 1; v <= num_ver; v++) {
if (!visited[v] && A[u][v] != MAX_VALUE && D[u] + A[u][v] < D[v]) {
D[v] = D[u] + A[u][v];
}
}
}

for (int i = 1; i <= num_ver; i++) {
System.out.println(“Distance of source ” + s + ” to ” + i + ” is ” + D[i]);
}
}

public static void main(String[] args) {
int n = 0, s;
Scanner sc = new Scanner(System.in);
System.out.println(“Enter the number of vertices:”);
n = sc.nextInt();
int A[][] = new int[n + 1][n + 1];
System.out.println(“Enter the Weighted Matrix:”);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
A[i][j] = sc.nextInt();
if (i == j) {
A[i][j] = 0;
continue;
}
if (A[i][j] == 0) {
A[i][j] = MAX_VALUE;
}
}
}
System.out.println(“Enter the source vertex”);
s = sc.nextInt();
Dijkstra dijkstra = new Dijkstra(n);
dijkstra.shortest(s, A);
sc.close();
}
}