Purchase Solution

Greedy strategy to find shortest path between two vertices

Not what you're looking for?

Ask Custom Question

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.

View More Free Quizzes
Related BrainMass Solutions

  • Three Algorithm True or False Questions

    The path in T between any pair of vertices v_1 and v_2 must be a shortest path in G. True or False?

  • Graphs and their adjacency matrices. Trees

    Find the number of simple paths connecting two concrete vertices in this graph. Find the the shortest simple path connecting these vertices. Construct the tree corresponding to the given structure of the college staff.

  • weighted directed graph

    20212 Give an example of a weighted directed graph with at most 5 vertices such that Dijkstra's algorithm will NOT give the correct results for the shortest path lengths from source s to every other vertex.

  • parent array produced by Dijkstra's algorithm

    It does not always work : Consider a graph with 5 vertices, A, B, C, D and these edge weights: A->B : 1 B->C : 1 C->D : -2 A->D : 3 The shortest path A to D should be A->B->C->D (weight 0) But the algorithm will find the path A->D (weight 3

  • Shortest Path Problem

    54486 Shortest Path Problem 1 a. Three cities are at the vertices of and equilateral triangle of unit length. Flying Executive Airlines needs to supply connecting services between these three cities.

  • Trigonometry

    The shortest distance between two points is a straight line. Since and , so The triangle is a right triangle. The shortest distance between C and A is 32.47 meters. 2.

  • Shortest path between two points on a plane.

    146613 Shortest path between two points on a plane. Let A = (0, 1) and B = (3, 2) be points on a plane. What is the length of the shortest path from A to the x-axis to B?

  • Quantative Analysis Network models: Shortest route technique

    The objective is to find the shortest path from the origin to the destination.

  • Graph proofs

    V_1 and V_2 are two partition of the Graph. Let a and b two vertex of the graph such that a belongs to V_1 and b belongs to V_2. By definition of the connected graph there is a path from any vertex of the graph to another vertex of the graph.

View More Related Solutions