2
$\begingroup$

Given a connected graph $G=(X,E)$ with positive edge weights. We assume that $G$ contains a unique min weight spanning tree $T_{\min}$ (this is true for example when for all the cuts, the edge with the minimum weight is unique). What is the necessary and sufficient condition that insures that the following holds: There exists a vertex $x$ for which the shortest path tree obtained by starting Dijkstra from $x$ coincides with $T_{\min}$.

Example:

Without the uniqueness assumption, here is an example graph
A graph instance whose MST differs from any SPT
The following R code shows that every shortest path tree must use an inner edge that is not part of any MST:

x<-c(1,2, 1,8, 2,3, 2,11, 3,4, 4,5, 4,10, 5,6, 6,7, 6,12, 7,8, 8,9,   
   #inner edges that are not part of MST due to their relatively big   weight   
   9,10, 11,12)   
m<-matrix(x,byrow = T, ncol = 2)   
y <- c(2,2,2,1,2,2, 1,2,2,1,2,2,   
     #inner edge weights   
     3.5,3.5)   
arcs <- cbind(m,y)   
#we check only for the three vertices, the others are symetrical to them   
for(i in c(1,2,9)){   
   cat("\n Source:",i,"\n")   
   getShortestPathTree(nodes, arcs, algorithm = "Dijkstra", source.node = i, directed = FALSE)   
}   
$\endgroup$
9
  • 1
    $\begingroup$ Since every shortest-path tree can be found by Dijkstra, that property is the same as "$T_{\min}$ is a shortest-path tree for some vertex." $\endgroup$ – John L. Apr 12 '20 at 17:17
  • $\begingroup$ I must learn how to edit my comments to display source codes. $\endgroup$ – Mahdaoui7 Apr 13 '20 at 11:59
  • $\begingroup$ I meant, "there exists a vertex 𝑥 for which the shortest path tree obtained by starting Dijkstra from $x$. coincides with $T_{\min}$" is the same as "$T_{\min}$ is a shortest-path tree for some vertex." $\endgroup$ – John L. Apr 13 '20 at 14:26
  • $\begingroup$ I think that I was able to prove that with the uniqueness assumption there is always an SPT that coincides with the unique MST. Is this result already known/proven? $\endgroup$ – Mahdaoui7 Apr 14 '20 at 9:57
  • 1
    $\begingroup$ Consider graph with AB=2, BC=2, CD=2, DA=3, AC=3, BD=3. The unique MST is {AB, BC, CD}. Every SPT will include either AC or BD, an edge that is not in the unique MST. $\endgroup$ – John L. Apr 14 '20 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.