For this assignment, you are going to implement an algorithm invented by Edsgar

Question

For this assignment, you are going to implement an algorithm invented by Edsgar Dijkstra to compute the shortest path in a network from a starting node to all other nodes. An excellent description of the algorithm, along with an animation, can be found at en.wikipedia.org (as Dijkstra's Algorithm). In this problem, you will be given the description of some number of graphs and for each graph you will determine the shortest path from the specified node to all other nodes. Each graph description will start with an integer NC specifying the number of connections (edges) between the nodes. A NC value of zero marks the end of the input data. Following NC, there will be NC lines each containing three positive integers. The first two numbers are nodes pairs and the third number is the weight of the edge. There will not be more than one edge between any pair of nodes, and no graph will contain more than 100 nodes. Following each configuration, there will a single node specified as the starting node for your path computations. For example, consider the testfile: 9 1 2 7 1 3 9 1 6 14 2 3 10 2 4 15 3 4 11 3 6 2 5 6 9 4 5 6 1 5 1 2 10 2 4 10 3 2 2 4 3 2 5 6 8 2 0 This specifies two graphs. The first graph is the one from the wikipedia page. It has 9 edges, all with associated weights. The starting node for this graph is 1. The second graph has 7 edges and the search starts at node 2. Note that this graph is disconnected - hence some of the nodes do not have distances. Sample output for this file would be: Result from node 1 Node 1: dist = 0, previous = -1 Node 2: dist = 7, previous = 1 Node 3: dist = 9, previous = 1 Node 6: dist = 11, previous = 3 Node 4: dist = 20, previous = 3 Node 5: dist = 20, previous = 6 Result from node 2 Node 1: dist = 10, previous = 2 Node 2: dist = 0, previous = -1 Node 4: dist = 4, previous = 3 Node 3: dist = 2, previous = 2 Node 5: dist = 1000000, previous = -1 Node 6: dist = 1000000, previous = -1 Do not make any assumptions about the node numbers used for a graph except that they will all be > 0. All input is syntatically and semantically correct. There are several constraints on your solution. Failure to follow constraint #1 will result in a failing grade. <strong>You may not use any arrays (other than strings). </strong>Your data structure will be dynamically allocated and connected via pointers. Your solution will dynamically allocate linked lists to represent the graph. One suggestion is to have a main linked list with a struct for each node in the graph. In my implementation, each of these has a linked list of neighbors. You must free all allocated space once you are done with a graph. Your code must have comments that allow me to figure out how you are using the data structures you have defined.

Explanation / Answer

/* Program of shortest path between two node in graph using Djikstra algorithm */ #include #define MAX 10 #define TEMP 0 #define PERM 1 #define infinity 9999 struct node { int predecessor; int dist; /*minimum distance of node from source*/ int status; }; int adj[MAX][MAX]; int n; void main() { int i,j; int source,dest; int path[MAX]; int shortdist,count; create_graph(); printf("The adjacency matrix is : "); display(); while(1) { printf("Enter source node(0 to quit) : "); scanf("%d",&source); printf("Enter destination node(0 to quit) : "); scanf("%d",&dest); if(source==0 || dest==0) exit(1); count = findpath(source,dest,path,&shortdist); if(shortdist!=0) { printf("Shortest distance is : %d ", shortdist); printf("Shortest Path is : "); for(i=count;i>1;i--) printf("%d->",path[i]); printf("%d",path[i]); printf(" "); } else printf("There is no path from source to destination node "); }/*End of while*/ }/*End of main()*/ create_graph() { int i,max_edges,origin,destin,wt; printf("Enter number of vertices : "); scanf("%d",&n); max_edges=n*(n-1); for(i=1;i n || destin > n || origin

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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