The greedy algorithm presented in this problem is not guaranteed to find the shortest path between vertices in graph. This can be seen by counterexample. Consider the following weighted graph: \par \begin {picture}(300,100) \par \put (200,75){\circle {20}} \put (198,73){A} \put (193,68){\line (-5,-1){82}} \put (145,63){1} \put (207,68){\line (5,-1){82}} \put (255,63){2} \put (100,50){\circle {20}} \put (98,48){B} \put (107,43){\line (5,-1){82}} \put (145,25){3} \put (300,50){\circle {20}} \put (298,48){C} \put (293,43){\line (-5,-1){82}} \put (255,25){1} \put (200,25){\circle {20}} \put (198,23){D} \par \end {picture} \par Suppose we wish to find the shortest path from $start=A$ to $goal=D$ and we make use of the proposed greedy strategy. Starting at $A$ and with $path$ initialized to $A$, the algorithm will next place $B$ in $path$ (because $(A,B)$ is the minimum cost edge incident on $A$) and set $start$ equal to $B$. The lightest edge incident on $start=B$ which has not yet been traversed is $(B,D)$. As a result, $D$ will be appended to $path$ and $start$ will be assigned $D$. At this point the algorithm will terminate (since $start=goal=D$). In the end we have that $path=A,B,D$, which clearly is not the shortest path from $A$ to $D$. (Note: in fact the algorithm is not guaranteed to find any path between two given nodes since it makes no provisions for backing up. In an appropriate situation, it will fail to halt.)