CSCI203 ASSIGNMENT 3

CSCI203 ASSIGNMENT 3
.Dijkstra's algorithm finds the shortest path from a given node to all other nodes.
1) We observe that we can modify this algorithm to stop as soon as a particular node is reached;
thus producing an algorithm to find the shortest path between a specific pair of points.
However, this algorithm may involve the consideration of a number of points which do not lie
on the final shortest path.
We now consider 2 alternatives:
2) We can modify the algorithm to add nodes to the solution based on an A* criterion derived
from the Euclidean (straight line) distance from each candidate node to the desired end node.
3) We can attempt to improve our efficiency by modifying Dijkstra's algorithm to start at both
the source and destination nodes and to construct two partial solution trees in parallel until
one node is in both partial solution trees.
Your task is to:
1. Code the modified Diskstra's algorithm to search from the start node out.
2. Code the A* variant.
3. Code the proposed improved algorithm.
Input consists of the following data:
1) The number of nodes in the graph.
2) A set of triples containing the node number, its X-coordinate and its Y coordinate – one triple
for each node in the graph.
3) The number of edges in the graph.
4) A set of triples consisting of two node numbers and a cost – one triple for each edge in the
graph.
A pair of node numbers representing the start- and end -nodes between which paths must be found.
Output consists of the following data for each :
x The length of the shortest path from solution 1:
x The Path (list of nodes) from solution 1:
x The number of additional nodes in the solution tree for solution 1(those not in the shortest
path)
x The length of the shortest path from solution 2:
x The Path (list of nodes) from solution 2:
x The number of additional nodes in the solution tree for solution2(those not in the shortest
path)
x The length of the shortest path from solution 3:
x The Path (list of nodes) from solution 3:
x The number of additional nodes in the solution tree for solution 3(those not in the shortest
path)
Notes:
Program
In additi
discussio
approach
Where y
The follo
The graph is
Do not use t
The graph w
Your progra
specified no
ms must comp
not compile
with comme
ion to the sou
on of your re
hes and note
submit -u us
or
submit -u us
your unix use
owing image
s undirected s
the STL.
will not have
am should pri
des.
pile and run
and run will
ents.
urce file ass3
esults. You s
e any problem
ser -c csci203
ser -c csci203
er name shou
e shows the g
so each edge
more than 50
int an approp
under gcc (C
l receive no m
3.c or ass3.cp
should talk ab
ms that may a
3 -a 3 ass3.c
3 -a 3 ass3.cp
uld appear in
graph for wh
e connects th
0 nodes.
priate error m
C programs)
marks. Progr
pp you shoul
bout the relat
arise with ea
ass3.txt
pp ass3.txt
nstead of user
hich test data
he pair of nod
message if no
or g++ (C++
rams should b
ld also subm
tive efficienc
ach of them
r.
a is provided.
des specifies
o path exists
+ programs).
be appropria
it a text file c
cy of each of
.
in both direc
between the
Programs w
ately docume
containing a
f the three pr
ctions.
e
which do
ented
brief
roposed
Powered by