Description
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
