In an undirected, weighted graph G the set of shortest paths from an arbitrary start vertex s form a spanning tree of G. We're calling this spanning tree a shortest path tree.

How do I find an example to show that, even if all edge weights are different (and non-negative), it is possible to have more than one shortest paths tree?

  • 3
    $\begingroup$ Did you try to find a solution on your own? $\endgroup$ – quicksort Oct 31 '17 at 18:59
  • 1
    $\begingroup$ There's an almost trivial example with three nodes, have you tried to find it? $\endgroup$ – BlueRaja - Danny Pflughoeft Oct 31 '17 at 19:26
  • $\begingroup$ Whenever you ask something please mention what approach you have already tried. This community must be used when you are unable to find solution after a lot of tries. $\endgroup$ – Kishan Kumar Nov 1 '17 at 4:17

As mentioned by BlueRaja you can prove this with only three nodes.

Take 3 nodes (A,B,C) with the following edge weights:

A->B = 1

B->C = 2

A->C = 3

Now if you take A as source vertex and try to find the shortest paths you can get two different trees.

1- The edge AC and AB are present. Cost to C=3 and Cost to B=1.

2- The edge AB,BC are present. Cost to C=3 and Cost to B=1.

As you can see all edge weights are distinct yet we are getting two different shortest spanning trees.

The basic idea is that: Let C be the least cost of reaching a particular node in a spanning tree. Then it may be possible to find another path to C with the same cost if the sum of edge weights constituting the path is equal to C.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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