Let the length of a path in a weighted graph be the sum of t

Let the length of a path in a weighted graph be the sum of the weights of the edges in the

path. Suppose we want to nd a shortest path from vertex a to vertex d by the following greedy strategy:

starting from vertex a, we move to its neighbor who has the edge with the smallest weight among all the

neighors. For example, in the following graph Fig. 2, we want to compute the shortest path from a to

d. The resulting path by the greedy strategy is a-> b -> c -> d

which obviously is not the shortest

path. Why does this greedy strategy fail? Speci cally, do the two properties of greedy algorithms hold

in this case? Please explain the reason.

10 Figure 2: The weight of each edge is labeled

Solution

The \"greedy-choice property\" and \"optimal substructure\" are the two properties of greedy algorithms. Greedy choice property means that a globally optimal solution is found by making the greedy choice locally. Optimal substrucutre means that efficient solution can be obtained if we find optimal solutions of its subproblems.

In this case even if we proceed by choosing the least weighted edge presently, as we are not considering the weights of the edges later, the greedy choice property does not hold here.