# Untitled

unknown
plain_text
a month ago
2.4 kB
1
Indexable
Never
```import java.util.Arrays;

public class Main {

private static final int INF = Integer.MAX_VALUE;

public void dijkstra(int[][] graph, int source) {
int n = graph.length;
int[] dist = new int[n]; // array to store shortest distances
boolean[] visited = new boolean[n]; // array to mark visited nodes
int[] pred = new int[n]; // array to store predecessors

Arrays.fill(dist, INF); // initialize distances as infinity
dist[source] = 0; // distance from source to source is 0

for (int i = 0; i < n - 1; i++) {
// select the vertex with the minimum distance
int u = minDistance(dist, visited);
visited[u] = true; // mark the vertex as visited

// update distances of adjacent vertices
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != 0 && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
pred[v] = u; // store predecessor
}
}
}
printPathAndDistances(source, dist, pred); // print the shortest path and distances
}

// helper function to find the vertex with the minimum distance
private int minDistance(int[] dist, boolean[] visited) {
int minDist = INF;
int minVertex = -1;

for (int i = 0; i < dist.length; i++) {
if (!visited[i] && dist[i] < minDist) {
minDist = dist[i];
minVertex = i;
}
}
return minVertex;
}

// helper function to print the shortest path and distances
private void printPathAndDistances(int source, int[] dist, int[] pred) {
System.out.println("Shortest distances from the source:");
for (int i = 0; i < dist.length; i++) {
System.out.println("Vertex " + i + ": " + dist[i]);
if (dist[i] != INF) {
System.out.print("Path: " + i);
int predVertex = pred[i];
while (predVertex != source) {
System.out.print(" <- " + predVertex);
predVertex = pred[predVertex];
}
System.out.println(" <- " + source);
}
}
}

public static void main(String[] args) {
int[][] graph = {
{ 0, 2, 0, 1, 0 },
{ 2, 0, 4, 3, 0 },
{ 0, 4, 0, 0, 6 },
{ 1, 3, 0, 0, 5 },
{ 0, 0, 6, 5, 0 },
};
Main dijkstra = new Main();
dijkstra.dijkstra(graph, 0);
}
}
```