# 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. Commented Sep 17, 2016 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
Commented Sep 17, 2016 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 Commented Sep 18, 2016 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? Commented Sep 18, 2016 at 12:39
• A graph consisting of a single edge is an obvious example. Commented Sep 19, 2016 at 12:54