Greedy strategy for finding a shortest path

Assignment Help Data Structure & Algorithms

Reference no: EM1380122

Question: Think about the given greedy strategy for finding a shortest path from vertex start to vertex goal in a connected graph.

1: Initialize path to start.
2: Initialize Visited Vertices to {start}.
3: If start=goal, return path and exit. Otherwise, continue.
4: Find the edge (start,v) of the minimum weight such that v is adjacent to start and v is not in Visited Vertices.
5: Add v to path.
6: Add v to Visited Vertices.
7: Set start equal to v and go to step 3.

Does this greedy strategy find the shortest path from start to goal?
Either explain intuitively why it works, or give a counter-example showing why it does not.

Reference no: EM1380122

Questions Cloud

Determine average waiting time for constant length messages : Messages reach at random to be sent across a communications link with a information rate of 9600 bps. The link is 70 percent utilized, and the average message length is 1000 octets.

Find the number of physicians : Find the number of physicians to be located in each of the areas if the physicians are income maximizers - Population Index

Find the db strength of the signal : A signal starts at x point. As it travels to y point it loses eight db. At point y the signal is boosted by ten db. As the signal travels to point z it loses 7 db.

Terminal and the corresponding data center : 2-information centers used for retail credit authorization are located in 2-different major population centers, which are separated from each other through a large zone of very little population.

Greedy strategy for finding a shortest path : Think about the given greedy strategy for finding a shortest path from vertex start to vertex goal in a connected graph.

Prepare a monthly operating budget for the dmv : What other changes would you suggest that might help the DMV's situation and what are the advantages and disadvantages of the various suggested changes

Time sharing operating system : Assume a time sharing operating system allocated time slices of twenty milliseconds and the machine executed an average of 5000 instructions per microsecond.

Data speed effect on fundamental business decisions : Can the speed in which data is transmitted have an adverse effect on fundamental business decisions? Yes, speed that is traveling at big rates of speed can have an affect on fundamental business decisions.

Draw a time line to show the cash flows of the project : Draw a time line to show the cash flows of the project and compute the project's payback period, net present value, profitability index, and internal rate of return.

User Account

All Pages