# Finding multiple shortest path trees from an undirected, weight graph

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?

• Did you try to find a solution on your own? – quicksort Oct 31 '17 at 18:59
• There's an almost trivial example with three nodes, have you tried to find it? – BlueRaja - Danny Pflughoeft Oct 31 '17 at 19:26
• 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. – 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.