0
$\begingroup$

Suppose:

$x_1,x_2,x_3,x_4$ is a shortest path from $x_1$ to $x_4$

$x_2,x_5,x_6,x_7,x_9$ is a shortest path from $x_2$ to $x_9$

$x_{10},x_5,x_8,x_3,x_9$ is a shortest path from $x_{10}$ to $x_9$

Which of the following is/are true?

(a) $x_1,x_2,x_5,x_6,x_7,x_9$ is a shortest path from $x_1$ to $x_9$

(b) The length of $x_5,x_6,x_7,x_9$ must be the same as $x_5,x_8,x_3,x_9$

(c) At least one edge in the graph must have 0 length

I'm confused as to how to work out these conceptually. I thought (a) was true, but it turns out that it's false. I don't understand why (b) must be true, nor why (c) must be false. If anyone can outline a procedure that will help me with this problem, and just understanding the shortest path in general, I'd greatly appreciate it.

The solution says that, for (b), "the subpath of the shortest path is also a shorest path." Can someone explain what this means, and how I can recognize that this is actually true?

Thank you.

  • 0
    Should (b) say "...must be the same *length*..."?2012-12-18

2 Answers 2

1

The key to this problem is the fact that if $a,..., b, ..., c$ is a shortest path from $a$ to $c$, then $a,.., b$ and $b,..,c$ are shortest paths from $a$ to $b$ and $b$ to $c$.

Why is b) true

$x_2,x_5,x_6,x_7,x_9$ is a shortest path from $x_1$ to $x9$. Then $x_5,x_6,x_7,x_9$ is a shortest path from $x_5$ to $x9$.

$x_{10},x_5,x_8,x_3,x_9$ is a shortest path from $x_{10}$ to $x9$. Then $x_5,x_8,x_3,x_9$ is a shortest path from $x_5$ to $x9$.

But any two shortest paths from $x_5$ to $x_9$ must have the same length.

It is easy to construct counterexamples for $a)$ and $c)$...

Counterexamples for a) and c)

For c) it is easy. For $a)$, just make sure that $x_1,x_2,x_5$ is not the shortest path from $x_1$ to $x_5$. So if you build any graph for which $a)$ is true, just add an edge $x_1x_5$ of length just a tiny bit smaller that $x_1x_2+x_2x_5$....

  • 0
    Can you provide counterexamples for (a) and (c), because the source of my confusion is from these too. Shouldn't $x_1, x_2$ be a shortest path as well? And if $x_1, x_2$ is a shortest path, as well as $x_2, x_5, x_6, x_7, x_9$, shouldn't $x_1, x_2, x_5, x_6, x_7, x_9$ be a shortest path as well?2012-12-18
0

(b) The length of $x_5,x_6,x_7,x_9$ must be the same as $x_5,x_8,x_3,x_9$

Note that $x_5,x_6,x_7,x_9$ is a subpath of $x_2,x_5,x_6,x_7,x_9$ which is stated as the shortest path from $x_2$ to $x_9$. Also $x_5,x_8,x_3,x_9$ is a subpath of the shortest path from $x_{10}$ to $x_9$. If (b) were false, then one of these would not be the shortest path between the given vertices.