Answered step by step
Verified Expert Solution
Link Copied!

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;
edge(edge * e =0, struct vertex * v =0, int w =0)
1
{ Vertex = v; weight = w; nextedge = e;}
};
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?
>";
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()){
/* supply code to build the edge list */
}
// Output the graph
vptr = graph;
while( vptr ){
cout << vptr->name <<
;
edgeptr = vptr->edgelist;
while( edgeptr ){
cout <<" Edge to "<< edgeptr->Vertex->name
<<" with weight "<< edgeptr->weight <<
;
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.
";
return 1;
}
if(!finishptr ){
cout << "Finish point given is not a valid vertex.
";
return 1;
}
last = startptr;
last->index =0;
last->final = true;
while(!(finishptr->final)){
/* supply code to search for shortest path */
}
3
vptr = finishptr;
if ( vptr->pre )
while( vptr ){
cout << vptr->name <<
;
vptr = vptr->pre;
} else
cout <<"No such path.
";
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.
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.
4
Dijkstras Algorithm
PROCEDURE SHORTESTPATH
begin SHORTESTPATH
v G
while (v = NIL)
INDEX(v)\infty
FINAL(v) false
v NEXTVERTEX(v)
INDEX(s)0
FINAL(s) true
last s
while ( FINAL(f))
x EDGELIST(last)
while (x = 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)
if (there is no vertex with finite INDEX and FINAL = false.)
PRE(f) NIL
break
else
Let w be any vertex with minimal INDEX and FINAL = false.
FINAL(w) true
last w
If PRE(f)= 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.

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Driven Web Sites

Authors: Mike Morrison, Joline Morrison

1st Edition

061901556X, 978-0619015565

More Books

Students also viewed these Databases questions