import java.util.
*;
public class DijkstraAlgorithm {
static class Node implements Comparable<Node> {
int vertex;
int distance;
Node(int vertex, int distance) {
this.vertex = vertex;
this.distance = distance;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.distance, other.distance);
}
}
public static int[] dijkstra(int[][] graph, int start) {
int numVertices = graph.length;
int[] distances = new int[numVertices];
boolean[] visited = new boolean[numVertices];
PriorityQueue<Node> minHeap = new PriorityQueue<>();
Arrays.fill(distances, Integer.MAX_VALUE);
distances[start] = 0;
minHeap.add(new Node(start, 0));
while (!minHeap.isEmpty()) {
Node current = minHeap.poll();
int u = current.vertex;
if (visited[u]) {
continue;
}
visited[u] = true;
for (int v = 0; v < numVertices; v++) {
if (graph[u][v] != 0 && !visited[v]) {
int newDist = distances[u] + graph[u][v];
if (newDist < distances[v]) {
distances[v] = newDist;
minHeap.add(new Node(v, newDist));
}
}
}
}
return distances;
}
public static void main(String[] args) {
int[][] graph = {
{0, 7, 9, 0, 0, 14},
{7, 0, 10, 15, 0, 0},
{9, 10, 0, 11, 0, 2},
{0, 15, 11, 0, 6, 0},
{0, 0, 0, 6, 0, 9},
{14, 0, 2, 0, 9, 0}
};
int startVertex = 0;
int[] distances = dijkstra(graph, startVertex);
System.out.println("Shortest distances from vertex " + startVertex + ":");
for (int i = 0; i < distances.length; i++) {
System.out.println("To vertex " + i + " : " + distances[i]);
}
}
}
