Dijkstra's algorithm in java
On-campus and online computer science courses to Learn the basic concepts of Computer Science.This tutorial will cover c ,c++, java, data structure and algorithm,computer graphics,microprocessor,analysis of algorithms,Digital Logic Design and Analysis,computer architecture,computer networks,operating system.
code in Java:import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class Graph { int nodes; int edges; int grph[][]; void accept() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter number of nodes: "); nodes = Integer.parseInt(br.readLine()); System.out.println("Enter number of edges: "); edges = Integer.parseInt(br.readLine()); grph = new int[nodes][nodes]; for(int i = 0; i < nodes; i++) for(int j = 0; j < nodes; j++) grph[i][j] = 9999; for(int i = 0; i < edges; i++) { System.out.println("Enter source node for edge " + (i + 1)); int source = Integer.parseInt(br.readLine()); System.out.println("Enter destination node for edge " + (i + 1)); int destination = Integer.parseInt(br.readLine()); System.out.println("Enter the distance for traveling from node " + source + " to " + destination); int distance = Integer.parseInt(br.readLine()); grph[source - 1][destination - 1] = distance; grph[destination - 1][source - 1] = distance; } } } class Dijkstras { static void dijk(Graph g, int src) { int distance[] = new int[g.nodes]; int previous[] = new int[g.nodes]; String path[] = new String[g.nodes]; for(int i = 0; i < g.nodes; i++) { distance[i] = 9999; previous[i] = -1; path[i] = ""; } distance[src] = 0; for(int i = 0; i < g.nodes; i++) { for(int j = 0; j < g.nodes; j++) { if(distance[i] + g.grph[i][j] < distance[j]) { distance[j] = distance[i] + g.grph[i][j]; previous[j] = i; } } } for(int i = 0; i < g.nodes; i++) { int current = i; do { path[i] = "-" + (current + 1) + path[i]; current = previous[current]; } while(current != -1); path[i] = path[i].substring(1, path[i].length()); } System.out.println(); for(int i = 0; i < g.nodes; i++) { if(i != src) { System.out.println("The shortest path & its distance for node " + (i + 1) + " is:"); System.out.print("Path: " + path[i]); System.out.println(" Distance: " + distance[i]); } } } public static void main(String args[]) throws IOException { Graph g = new Graph(); g.accept(); dijk(g, 0); } }output:-
Enter number of nodes: 6 Enter number of edges: 9 Enter source node for edge 1 1 Enter destination node for edge 1 6 Enter the distance for traveling from node 1 to 6 14 Enter source node for edge 2 1 Enter destination node for edge 2 3 Enter the distance for traveling from node 1 to 3 9 Enter source node for edge 3 1 Enter destination node for edge 3 2 Enter the distance for traveling from node 1 to 2 7 Enter source node for edge 4 2 Enter destination node for edge 4 3 Enter the distance for traveling from node 2 to 3 10 Enter source node for edge 5 2 Enter destination node for edge 5 4 Enter the distance for traveling from node 2 to 4 15 Enter source node for edge 6 3 Enter destination node for edge 6 6 Enter the distance for traveling from node 3 to 6 2 Enter source node for edge 7 3 Enter destination node for edge 7 4 Enter the distance for traveling from node 3 to 4 11 Enter source node for edge 8 4 Enter destination node for edge 8 5 Enter the distance for traveling from node 4 to 5 6 Enter source node for edge 9 5 Enter destination node for edge 9 6 Enter the distance for traveling from node 5 to 6 9 The shortest path & its distance for node 2 is: Path: 1-2 Distance: 7 The shortest path & its distance for node 3 is: Path: 1-3 Distance: 9 The shortest path & its distance for node 4 is: Path: 1-3-4 Distance: 20 The shortest path & its distance for node 5 is: Path: 1-3-6-5 Distance: 20 The shortest path & its distance for node 6 is: Path: 1-3-6 Distance: 11 --------------------------------
0 comments: