1
$\begingroup$

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)...

$\endgroup$

1 Answer 1

1
$\begingroup$

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)$.

$\endgroup$
1
  • $\begingroup$ I see! Thanks for the response! Really appreciate it! $\endgroup$
    – pehperclip
    Commented Nov 19, 2023 at 11:23

Your Answer

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

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