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.

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

#include <stdio.h>

#include <limits.h>

#include<stdbool.h>

#define V 10

int minDistance(int dist[], bool sptSet[])

{

int min = INT_MAX, 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;

}

void printpath(int prev[],int src,int current)

{

if(current==src)return;

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

printf("-->%d",current);

}

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

{

int dist[V],i,count,v;

int prev[V];

bool sptSet[V];

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

dist[i] = INT_MAX, sptSet[i] = false,prev[i]=-1;

dist[src] = 0;

prev[src]=-1;

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

{

int u = minDistance(dist, sptSet);

sptSet[u] = true;

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

if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX

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

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

prev[v]=u;}

}

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

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

printpath(prev,src,dest);

}

int main()

{ int src,dest,i,j;

int graph[V][V];

printf(" Enter adjecent matrix : ");

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

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

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

scanf("%d",&graph[i][j]);

}

}

printf("Enter source and destination : ");

scanf("%d %d",&src,&dest);

dijkstra(graph,src,dest);

return 0;

}

for any query please comment.

please upvote if find it helpful.

Thank you!.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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