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 $=\backslash 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

graph$1.$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 graph$2.$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$

Dijkstra$$s Algorithm

PROCEDURE SHORTESTPATH

begin SHORTESTPATH

v $$ G

while $($v $=$ NIL$)$

INDEX$($v$)\backslash$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.