I need code that uses a weighted graph, completed using Dijkstra’s Algorithm

It needs to complete the code in the pdf, it can’t modify the given code at all, and it needs to implement Dijkstra’s Algorithm. 

Get Help With a similar task to - I need code that uses a weighted graph, completed using Dijkstra’s Algorithm

Login to view and/or buy answers.. or post an answer
Additional Instructions:

CS 341 Machine Problem 4 Due Monday May 18 at noon This assignment will not be accepted late under any circumstances! For this machine problem you should write code to input a weighted graph edge by edge along with the weight of each edge. The graph should be maintained as an edge list as discussed in the online lecture notes. Your program should prompt you for the name of a file that contains the data that defines the graph. Next your program will prompt you for the starting vertex and the destination index. These would be input from the command line. To complete the program, add code to implement the algorithm discussed in the online lecture notes to find the shortest path through the graph. The program should print out the shortest path (you may choose to print the path out in “reverse order”). Your code should be well organized and well documented. If no such path exists your program should print out that no such path exists. The program that you write must be written by filling in the missing code. No changes to the existing code is allowed. You should not declare any new variables. You should not use an adjacency matrix and you should not use a priority queue. Your program should closely follow the algorithm discussed in the online lecture notes a copy of which is included in this assignment for your convenience. In addition, your program should be written by filling in the missing parts, where indicated, of the following program. No changes to the given code are allowed. #include<fstream> #include<iostream> using namespace std; struct edge {struct vertex * Vertex; int weight; edge * nextedge; edge(edge * e = 0, struct vertex * v = 0, int w = 0) { Vertex = v; weight = w; nextedge = e;} 1 }; struct vertex {char name; vertex * nextvertex ; edge * edgelist; int index; bool final; vertex * pre; vertex(char n = ’\0’, vertex * v = 0) {name = n; nextvertex = v; edgelist = 0; index = -1; final = false; pre = 0;} }; int main(){ char input_file[128]; cout << "In what file is the data for the graph contained?\n> "; cin.getline(input_file, 128); ifstream infile( input_file ); vertex * graph = 0; vertex * startptr = 0, * finishptr = 0; vertex * vertexsearch = 0, * vptr = 0; vertex * last; vertex * w; edge * edgeptr = 0; int weight; char start, finish, comma; bool startnotfound = true, finishnotfound = true; infile >> start >>comma >> finish >> comma >> weight; while( !infile.eof() ){ /* build the edge list */ } // Output the graph vptr = graph; while( vptr ){ cout << vptr->name << ’\n’; edgeptr = vptr->edgelist; while( edgeptr ){ cout << " Edge to " << edgeptr->Vertex->name << " with weight " << edgeptr->weight << ’\n’; edgeptr = edgeptr->nextedge; } 2 vptr = vptr->nextvertex; } // From where to where cout << "From where: "; cin >> start; cout <<"to where: "; cin >> finish; vertex * s = graph; startptr = finishptr = 0; while( s ){ if( s->name == start ){ startptr = s; } if (s->name == finish ){ finishptr = s; } s = s->nextvertex; } if( !startptr ){ cout << "Start point given is not a valid vertex.\n"; return 1; } if( !finishptr ){ cout << "Finish point given is not a valid vertex.\n"; return 1; } last = startptr; last->index = 0; last->final = true; while( !(finishptr->final) ){ /* Search for shortest path */ } vptr = finishptr; 3 if ( vptr->pre ) while( vptr ){ cout << vptr->name << ’\n’; vptr = vptr->pre; } else cout << "No such path.\n"; return 0; } You should test your program against the following test data. The file graph1.dat should contain: a,b,1 a,c,4 b,c,2 c,b,2 b,d,7 b,e,5 c,e,1 d,e,3 e,d,3 d,z,2 e,z,6 You should search from a to z, from a to c from c to z and from e to a. The file graph2.dat should contain: a,b,23 a,c,10 c,b,5 You should search from a to b, from a to c and from c to a. 4 Dijkstra’s Algorithm PROCEDURE SHORTESTPATH begin SHORTESTPATH v ←− G while (v 6= NIL) INDEX(v) ←−∞ FINAL(v) ←− false v ←− NEXTVERTEX(v) INDEX(s) ←− 0 FINAL(s) ←− true last ←− s while (¬ FINAL(f)) x←− EDGELIST(last) while (x 6= NIL) v ←− VERTEX(x) if (¬ FINAL(v) ∧ INDEX(v) > INDEX(last) + LENGTH(x)) INDEX(v) ←− INDEX(last) + LENGTH(x) PRE(v) ←− last x←− NEXTEDGE(x) Let w be any vertex with minimal INDEX and FINAL = false. FINAL(w) ←− true. last ←− w 5

Related Questions

Similar orders to I need code that uses a weighted graph, completed using Dijkstra’s Algorithm
43
Views
0
Answers
PG2 – LAB 2: BLACKJACK OBJECTS
CONTENTS Overview........................................................................................................................................................................2 Part A - Classes......................................................
24
Views
0
Answers
Excel Project with Documentation
In a new sheet, create one-variable data tables for these food items. For each previously selected food item, create a two-variable data table that calculates the amounts of calories based on various portion sizes and the number of portions. I have att...
52
Views
0
Answers
Computer Vision - (Machine Learning, Artificial Intelligence field) assignment in python
Video processing, image processing, object detection, object tracking, background removel. It needs to be in PYTHON. Objective The goal of this project is to develop an automatic system for video analysis of footages for the game of curling. The system...
19
Views
0
Answers
Writing and understanding simple java program code
I need help writing a java program with an Eclipse IDE. Once written I need to identify, objects, lists, algorithms, set of instructions, anything that explains how the code is written, what it does, and how an end user will use it...