4
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Sep 17 '16 at 21:15
  • 1
    $\begingroup$ 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. $\endgroup$ – Evil Sep 17 '16 at 22:07
  • $\begingroup$ 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 $\endgroup$ – wilbertonunez Sep 18 '16 at 5:35
  • 1
    $\begingroup$ How about a 2-2-1 triangle with the shortest path tree rooted opposite the shortest edge? Is there something I am missing? $\endgroup$ – John Dvorak Sep 18 '16 at 12:39
  • 1
    $\begingroup$ A graph consisting of a single edge is an obvious example. $\endgroup$ – j_random_hacker Sep 19 '16 at 12:54
2
$\begingroup$

Let A-B-C be connected graph with edges like shown (AB and BC) the shortest path (the only possible) from A to C is through B. To include all vertices in the maximum spanning tree all vertices are needed, so this is small example (the smaller, A-B is also valid).

Maximum spanning tree have maximal weights, but may be not unique for given graph. The shortest path tree (which I assume is the weighted one) have path weights but also is not guaranteed to be unique.

From the definitions finding graph with cycles will be harder - taking minimal example, a full graph with vertices D, E, F and distances |DE| = 3, |EF| = 2, |DF| = 3, the shortest path from E to F is 2, but the maximal spanning tree will not contain this edge.
The two structures may overlap when there are no cycles or weights are equal, otherwise they will get opposite edges when possible.

$\endgroup$

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.