Explore BrainMass

Explore BrainMass

    Greedy strategy to find shortest path between two vertices

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com June 3, 2020, 1:39 am ad1c9bdddf

    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.