I am currently facing a question "Can a graph with a unique MST product a different spanning graph using Dijkstra vs using Prim's algorithm?" The answer is false and I am struggling to understand why (and also to come up with a counter example)...
1 Answer
$\begingroup$
$\endgroup$
1
A graph with a unique MST $T$ can definitely have a SPT that differs from $T$.
In fact, there are graphs where both the MST and the SPT (from a given source) are unique (so it doesn't matter which algorithms you use to compute them) and these two trees differ.
Consider for example a triangle graph with vertices $1,2,3$ and edge weights $w(1,2)=w(2,3)=2$, $w(1,3)=3$. The only MST contains the edges $(1,2)$ and $(2,3)$. The only SPT from $1$ contains the edges $(1,2)$ and $(1,3)$.
-
$\begingroup$ I see! Thanks for the response! Really appreciate it! $\endgroup$ Nov 19 at 11:23