Greedy strategy to find shortest path between two vertices
Not what you're looking for?
Consider the following greedy strategy for finding a shortest path from vertex start to vertex goal in a connected graph.
1: Initialize path to start.
2: Initialize VisitedVertices 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 VisitedVertices.
5: Add v to path.
6: Add v to VisitedVertices.
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.
Purchase this Solution
Solution Summary
Two examples are provided along with sufficient explanation.
Solution Preview
This greedy strategy does not find the "shortest path" from start to goal, as there is no guarantee that the decision that looks best at current level (influenced by only partial information) will indeed be so as we do not have complete picture. To be able to compare paths with respect to their weights, we need to have complete ...
Purchase this Solution
Free BrainMass Quizzes
C++ Operators
This quiz tests a student's knowledge about C++ operators.
C# variables and classes
This quiz contains questions about C# classes and variables.
Java loops
This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.
Inserting and deleting in a linked list
This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.
Excel Introductory Quiz
This quiz tests your knowledge of basics of MS-Excel.