Discussion Forum

Exercise 4 shortest simple paths

Exercise 4 shortest simple paths

av Thana Sriviriyakul -
Antal svar: 2

Since a subpath of a simple path is simple. Does the exercise want to ask that a subpath from vi to vj of a simple path might not be the shortest path from vi to vj instead? (no requirement on being simple) otherwise we're just comparing against simple paths.

Som svar till Thana Sriviriyakul

Sv: Exercise 4 shortest simple paths

av Anna Lindeberg -
Hi! To show that a particular subpath is not the shortest simple path between two vertices, you either show that the path is not simple, or that it is not the shortest path between its endpoints. In this case, the subpath is indeed necessarily simple, so you must show (eg by example) it can happen that it is not a shortest path (but the question is not posed wrongly, I would say).