Use Dijkstra’s algorithm to implement a program that computes the shortest dista

Question

Use Dijkstra’s algorithm to implement a program that computes the shortest distance between two nodes of an undirected weighted graph. Once Dijsktra’s algorithm has executed, use its output to automatically identify a shortest path in the graph. Please use java and a matrix graph

Input:

The graph, given by providing in sequence: the number of nodes, then a sequence of arcs with associated length.

The source.

The destination.

Output:

The shortest distance.

A shortest path.

- Dijkstra's algorithm computes the shortest distance from a selected node v to all the nodes of the graph. whereas in the programming assignment I ask you to compute the shortest distance from a source to a destination.

- Dijkstra's algorithm merely computes the shortest distance; I want you to also identify a shortest path. I will explain how to do this friday at the live session.

- To test your program/ to illustrate that it works, please use the following data. I assume that nodes are US airports (the ten largest airports in the US, as of the most recent survey). and I assume distances are actually airfares (hence they bear little relation to the actual geographic distances).

number of nodes: 10.

source: JFK.

destination: LAX.

airfares:

JFK CLT 80

JFK ORD 250

JFK DEN 310

CLT ORD 80

CLT DFW 260

CLT ATL 350

ATL DFW 60

ATL LAX 120

ORD DEN 70

ORD SFO 200

ORD LAS 310

DFW DEN 70

DEN LAX 280

LAS SEA 110

SEA SFO 210

SFO LAX 190

Hint: the simplest was to represent the weighted graph is by a symmetric 2D matrix, say dist[10,10] where dist(x,y) is the distance between x and y.

if there is no flight between x and y, you let dist[x,y] be infinity (i.e. a very large number).

Explanation / Answer

import java.util.*;

public class Dijkestra{

public static void main(String args[])

{ int src,dest,i,j,V;

Scanner input=new Scanner(System.in);
System.out.print("Enter number of vertices : ");

V=input.nextInt();
int graph[][]=new int[V][V];

System.out.printf(" Enter adjecent matrix : ");

for(i=0;i<V;i++){

for(j=0;j<V;j++){

System.out.printf(" Enter weight of path between %d and %d :",i,j);

graph[i][j]=input.nextInt();

}

}

System.out.printf("Enter source and destination : ");

src=input.nextInt();
dest=input.nextInt();

dijkstra(graph,src,dest,V);

}

public static int minDistance(int dist[], boolean sptSet[],int V)

{

int min = Integer.MAX_VALUE, min_index,v;

for ( v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <= min)

min = dist[v];
min_index = v;

return min_index;

}

public static void printpath(int prev[],int src,int current,int V)

{

if(current==src)return;

printpath(prev,src,prev[current],V);

System.out.print("-->"+current);

}

public static void dijkstra(int graph[][], int src,int dest,int V)

{

int dist[]=new int[V],i,count;

int prev[]=new int[V];

boolean sptSet[]=new boolean[V];

for ( i = 0; i < V; i++)

dist[i] = Integer.MAX_VALUE ;
sptSet[i] = false;
prev[i]=-1;

dist[src] = 0;

prev[src]=-1;

for (count = 0; count < V-1; count++)

{

int u = minDistance(dist, sptSet,V);

sptSet[u] = true;

for (int v = 0; v < V; v++)

if (sptSet[v]==false && graph[u][v]>=0 && dist[u] != Integer.MAX_VALUE

&& dist[u]+graph[u][v] < dist[v]){

dist[v] = dist[u] + graph[u][v];

prev[v]=u;}

}

System.out.printf("minimum distance path between %d and %d is: %d",src,dest,dist[dest]);

System.out.printf(" shorest path is : %d",src);

printpath(prev,src,dest,V);

}
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.