Answered step by step
Verified Expert Solution
Question
1 Approved Answer
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
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,
this should be done onlhy where indicated by the comments. 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
#include
using namespace std;
struct edge struct vertex Vertex; int weight; edge nextedge;
edgeedge e struct vertex v int w
Vertex v; weight w; nextedge e;
;
struct vertex char name; vertex nextvertex ; edge edgelist;
int index; bool final; vertex pre;
vertexchar n vertex v
name n; nextvertex v; edgelist ;
index ; final false; pre ;
;
int main
char inputfile;
cout In what file is the data for the graph contained?
;
cin.getlineinputfile, ;
ifstream infile inputfile ;
vertex graph ;
vertex startptr finishptr ;
vertex vertexsearch vptr ;
vertex last;
vertex w;
edge edgeptr ;
int weight;
char start, finish, comma;
bool startnotfound true, finishnotfound true;
infile start comma finish comma weight;
whileinfile.eof
supply code to build the edge list
Output the graph
vptr graph;
while vptr
cout vptrname
;
edgeptr vptredgelist;
while edgeptr
cout Edge to edgeptrVertexname
with weight edgeptrweight
;
edgeptr edgeptrnextedge;
vptr vptrnextvertex;
From where to where
cout "From where: ;
cin start;
cout to where: ;
cin finish;
vertex s graph;
startptr finishptr ;
while s
if sname start
startptr s;
if sname finish
finishptr s;
s snextvertex;
ifstartptr
cout "Start point given is not a valid vertex.
;
return ;
iffinishptr
cout "Finish point given is not a valid vertex.
;
return ;
last startptr;
lastindex ;
lastfinal true;
whilefinishptrfinal
supply code to search for shortest path
vptr finishptr;
if vptrpre
while vptr
cout vptrname
;
vptr vptrpre;
else
cout No such path.
;
return ;
You should test your program against the following test data. The file
graphdat should contain:
ab
ac
bc
cb
bd
be
ce
de
ed
dz
ez
You should search from a to z from a to c from c to z and from e to a
The file graphdat should contain:
ab
ac
cb
You should search from a to b from a to c and from c to a
Notice that this is a directed graph. The format for each edge in each of
the two data files is:
initial vertex, ending vertex, weight.
Dijkstras Algorithm
PROCEDURE SHORTESTPATH
begin SHORTESTPATH
v G
while v NIL
INDEXvinfty
FINALv false
v NEXTVERTEXv
INDEXs
FINALs true
last s
while FINALf
x EDGELISTlast
while x NIL
v VERTEXx
if FINALv INDEXv INDEXlast LENGTHx
INDEXv INDEXlast LENGTHx
PREv last
x NEXTEDGEx
if there is no vertex with finite INDEX and FINAL false.
PREf NIL
break
else
Let w be any vertex with minimal INDEX and FINAL false.
FINALw true
last w
If PREf NIL at the end of the execution of the algorithm then there
is no path from s to f Otherwise following the PRE pointers, starting at f
gives a desired shortest path in reverse order.
plese complete the full code
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started