Selesai

Dijkstra's algorithm to find the shortest path

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 Dijkstra'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.

5) A pair of node numbers representing the start and end nodes between which a path must be

found.

Output consists of the following data:

 The length of the shortest path from solution 1:

 The path (ordered list of nodes) from solution 1:

 The number of additional nodes in the solution tree for solution 1 (those not in the shortest

path that were added to the selected set):

 The length of the shortest path from solution 2:

 The path (ordered list of nodes) from solution 2:

 The number of additional nodes in the solution tree for solution2 (those not in the shortest

path that were added to the selected set):

 The length of the shortest path from solution 3:

 The path (ordered list of nodes) from solution 3:

 The number of additional nodes in the solution tree for solution 3 (those not in the shortest

path that were added to the selected set).

Notes:

The graph is undirected, so each edge connects the pair of nodes specified in both directions.

Do not use the STL.

The graph will not have more than 100 nodes.

Your program should print an appropriate error message if no path exists between the

specified nodes.

Programs must compile and run under g++ (C++ programs)

You should make a text file containing a brief discussion of your results. You should talk about the relative efficiency of each of the three proposed approaches and note any problems that may arise with each of them

Please refer the attached files for input data and graphs.

Keahlian: Algoritma, Pemrograman C, Pemrograman C++, CUDA, Java

Lihat lebih lanjut: dijkstra's shortest path algorithm in c, dijkstra algorithm c++, shortest path algorithm in data structure, shortest path algorithms, shortest path algorithm example, dijkstra algorithm java, shortest path problem example, dijkstra's algorithm youtube, shortest path algorithm javascript airline, shortest path algorithm java swing, apply shortest path algorithm google earth map asp net web site, dijkstra shortest path heaps java, java shortest path algorithm, job scheduling algorithm shortest path, shortest path algorithm directx, finding shortest path using algorithm dijkstra, algorithm shortest path, dijkstra algorithm shortest path, dijkstra's algorithm graph, dijkstra's algorithm shortest path

Tentang Pemberi kerja:
( 1 ulasan ) trichy, India

ID Proyek: #17956379

Diberikan kepada:

dobreiiita

Hello I am C++ and Algorithm expert and interested in this project.I have reviewed the requirements regarding graph algorithms and confident to handle it perfectly. I will keep codes simple and documented. Pl Lebih banyak

₹5000 INR dalam 7 hari
(516 Ulasan)
7.6

6 freelancer menawar dengan rata-rata ₹15463 untuk pekerjaan ini

dinhfreedom

Dear sir. Your project attracted my attention at first glance, because I've extensive experience in Shortest Path Programming. I'm really confident about your project, and very eager to join your project. If we have Lebih banyak

₹10000 INR dalam 3 hari
(44 Ulasan)
6.1
trutony

Hi, I am a talented C & C++ coder. I won the championship 4 times in Codechef. If you give me this project, you will get a good result. Thanks. Relevant skills & experiences: C & C++ Programming, Algorithm, Data proce Lebih banyak

₹10000 INR dalam 3 hari
(18 Ulasan)
5.2
mukesh30march

hello i read instruction that is given in this project please provide more detail for the project i have done number of project i will provide 5 star rating work thanks

₹7777 INR dalam 3 hari
(15 Ulasan)
3.4
idalarson

Dear client. I'm very experienced in algorithm. If you are unsure about me, please let me know immediately. Waiting your kind reply. Best regards.

₹30000 INR dalam 7 hari
(2 Ulasan)
1.5
₹30000 INR dalam 7 hari
(0 Ulasan)
0.0