# Can a shortest-path tree be a also maximum spanning tree?

If we were to find the shortest-path tree rooted at some vertex in a weighted graph G, is it possible that the resulting tree is also a maximum-weight spanning tree of G? Please give an example!

I tried every combination I could come up with using connected graphs with cycles on them (so that there is more than one possible path) and used Dijkstra's algorithm. No luck!

• What did you try? Where did you get stuck? We're happy to help with conceptual questions but just solving exercises for you is unlikely to really help. – David Richerby Sep 17 '16 at 21:15
• Maybe let us start again - what is the main problem? Why do you search for such example? What properties are required? About the edit, there is really no reason to include "EDIT:" into post, there is available history of changes. – Evil Sep 17 '16 at 22:07
• Hi! The main problem is to find a graph with 3 vertices or more in which Dijkstra's algorithm run at some vertex will find a maximum-weight spanning tree. The problem does not specify that the graph needs to contain cycles, so I guess your comment about the A-B-C vertices is a right answer. I am still curious though to find a tree with cycles where this also happens. @Evil – wilbertonunez Sep 18 '16 at 5:35
• How about a 2-2-1 triangle with the shortest path tree rooted opposite the shortest edge? Is there something I am missing? – John Dvorak Sep 18 '16 at 12:39
• A graph consisting of a single edge is an obvious example. – j_random_hacker Sep 19 '16 at 12:54