Untitled
import java.util.Arrays; public class Main { private static final int INF = Integer.MAX_VALUE; public void dijkstra(int[][] graph, int source, int destination) { 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 } } } printShortestPath(source, destination, dist, pred); // print the shortest path and distance } // 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 distance private void printShortestPath(int source, int destination, int[] dist, int[] pred) { System.out.print("Shortest path from " + source + " to " + destination + ": "); if (dist[destination] == INF) { System.out.println("No path exists."); return; } printPath(pred, destination); System.out.println("= " + dist[destination]); } // helper function to print the path from source to destination vertex private void printPath(int[] pred, int dest) { if (pred[dest] != -1) { printPath(pred, pred[dest]); System.out.print("-" + dest); } else { System.out.print(dest); } } 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, 4); // Call dijkstra method with source and destination vertices } }
Leave a Comment