Implement algorithm 18.2 (page 317), Dijkstra\'s algorithm as a C++, Java or Pyt
ID: 3681580 • Letter: I
Question
Implement algorithm 18.2 (page 317), Dijkstra's algorithm as a C++, Java or Python program.
https://web.njit.edu/~bm245/IT420/Computer-Networks-and-Internets-Fifth-Edition.pdf
Given:
A graph with a nonnegative weight assigned to each edge and a designated source node
Compute:
The shortest distance from the source node to each other node and a next-hop routing table
Method:
Initialize set S to contain all nodes except the source node;
Initialize array D so that D[v] is the weight of the edge from the source to v if such an edge exists, and infinity otherwise;
Initialize entries of R so that R[v] is assigned v if an edge exists from the source to v, and zero otherwise;
while (set S is not empty) {
choose a node u from S such that D[u] is minimum;
if (D[u] is infinity) {
error: no path exists to nodes in S; quit;
}
delete u from set S;
for each node v such that (u,v) is an edge {
if (v is still in S) {
c = D[u] + weight(u,v);
if (c < D[v]) {
R[v] = R[u];
D[v] = c;
}
}
}
}
Algorithm 18.2 A version of Dijkstra’s algorithm that computes R, a nexthop forwarding table, and D, the distance to each node from the specified source node.
Explanation / Answer
import java.util.Scanner;
public class Dijkstra {
int vertex[] = new int[10],dist[] = new int[10],pie[]= new int[100],v,graph[][] = new int[10][10],src;
void initialize(int src,int v) {
int i;
for(i=1;i<=v;i++) {
dist[i]=999; // it represents infinity
pie[i]=999;
}
dist[src]=0; //source is initialized to zero
}
void relax(int w,int from, int to) {
if(dist[to]>dist[from]+w) {
dist[to]=dist[from]+w;
pie[to]=from;
}
}
void disp(int x) {
if (pie[x]==src) {
System.out.println(src+"--"+x);
} else {
disp(pie[x]);
System.out.println(src+"--"+x);
}
}
public static void main(String[] args) {
int graph[][] = new int[10][10],v,i,j,k,l;
Dijkstra dx = new Dijkstra();
Scanner scan = new Scanner(System.in);
System.out.println("Enter the number of vertices (<10) : "); // array is declared with size of 10 only, u can change it
v = scan.nextInt();
if(v<=1) {
System.out.println("Enter a valid input");
}
System.out.println("Enter the graph matrix :");
for(i=1;i<=v;i++) {
for(j=1;j<=v;j++) {
if(i==j) {
graph[i][j]=0;
} else{
System.out.println(i+" to "+j);
graph[i][j] = scan.nextInt();
}
}
}
System.out.println("The entered weighted graph is :");
for(i=1;i<=v;i++) {
for(j=1;j<=v;j++) {
System.out.print(" "+graph[i][j]);
}
System.out.println();
}
System.out.println("Enter the source vertex : ");
dx.src = scan.nextInt();
dx.initialize(dx.src,v); //call initialization method
for(i=1;i<v;i++) {
for(k=1;k<=v;k++) {
for(j=1;j<=v;j++) {
dx.relax(graph[k][j],k,j);
}
}
}
for(k=1;k<=v;k++) {
for(j=1;j<=v; j++) {
if(dx.dist[j]>dx.dist[k]+graph[k][j]) {
System.out.println("Graph has negative cycle");
break;
}
}
}
System.out.println("The shortest distances are : ");
for(i=1;i<=v;i++) {
if(i!=dx.src) {
System.out.println(dx.src+" to "+i+" is "+dx.dist[i]);
System.out.println("Path is : ");
dx.disp(i);
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.