Share
Explore BrainMass

Greedy strategy to find shortest path between two vertices

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.

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

Solution Summary

Two examples are provided along with sufficient explanation.

$2.19