Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Should (b) say "...must be the same length..."? –  Code-Guru Dec 18 '12 at 3:37
add comment

2 Answers

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$....

share|improve this answer
    
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? –  user1903336 Dec 18 '12 at 3:39
add comment

(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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.