# 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

.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

You'll get 1 file (731.9KB)