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!

Improve this question
$\endgroup$
6
  • 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, 2016 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, 2016 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, 2016 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, 2016 at 12:39
  • 1
    $\begingroup$ A graph consisting of a single edge is an obvious example. $\endgroup$
    – j_random_hacker
    Sep 19, 2016 at 12:54

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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