Code modified dijkstra algorithm to search from start node

Assignment Help Data Structure & Algorithms
Reference no: EM132147904

Assignment - Dijkstra Algorithm

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 gcc (C programs), g++ (C++ programs), java or python.

Programs which do not compile and run will receive no marks. Programs should be appropriately documented with comments.

In addition to the source file ass3.c or ass3.cpp you should also submit 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.

Attachment:- Assignment Files.rar

Reference no: EM132147904

Questions Cloud

Pseudo code or a flowchart of your program : List above contains 26 fruits, each one with a name that begins with a different letter of the alphabet.
Which characteristics or approaches demonstrated by person : Which characteristics or approaches demonstrated by this person would you integrate into your own leadership style? Which ones would you prefer not to integrate
What data management considerations : What data management considerations must be reviewed to ensure success for both companies and assure regulatory compliance
Identify the given with a high risk of falling : Falls are one of the major causes of mortality and morbidity in older adults. Every year, an estimated 30-40% of patients over the age of 65 will fall at least.
Code modified dijkstra algorithm to search from start node : Assignment - Dijkstra Algorithm - Your task is to Code the modified Dijkstra's algorithm to search from the start node out
Determining the big-oh notation for the algorithm : What steps are required in determining the Big-Oh notation for the algorithm when sorting an array of integers
Troubleshoot reduced speed or latency : What are some other ways to troubleshoot reduced speed or latency? Or to find out what is using all the bandwidth? Perhaps might incorporate parts
Create an organizational culture in which employee feel safe : Create an organizational culture in which employees feel safe admitting or reporting on failure.
Discuss three concepts that you learned during the course : Advanced practice nurses should be able to critique, evaluate, and use theory. They should be able to integrate and apply a wide range of theories from nursing.

Reviews

Write a Review

Data Structure & Algorithms Questions & Answers

  Implement an open hash table

In this programming assignment you will implement an open hash table and compare the performance of four hash functions using various prime table sizes.

  Use a search tree to find the solution

Explain how will use a search tree to find the solution.

  How to access virtualised applications through unicore

How to access virtualised applications through UNICORE

  Recursive tree algorithms

Write a recursive function to determine if a binary tree is a binary search tree.

  Determine the mean salary as well as the number of salaries

Determine the mean salary as well as the number of salaries.

  Currency conversion development

Currency Conversion Development

  Cloud computing assignment

WSDL service that receives a request for a stock market quote and returns the quote

  Design a gui and implement tic tac toe game in java

Design a GUI and implement Tic Tac Toe game in java

  Recursive implementation of euclids algorithm

Write a recursive implementation of Euclid's algorithm for finding the greatest common divisor (GCD) of two integers

  Data structures for a single algorithm

Data structures for a single algorithm

  Write the selection sort algorithm

Write the selection sort algorithm

  Design of sample and hold amplifiers for 100 msps by using n

The report is divided into four main parts. The introduction about sample, hold amplifier and design, bootstrap switch design followed by simulation results.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd