-1
$\begingroup$

Is there any example that anybody could come up with that shows Prim's algorithm does not always give the correct result when it comes knowing the minimal spanning tree.

$\endgroup$
6
  • 1
    $\begingroup$ Prim's algorithm has a proof of correctness (see here). What exactly are you asking for? $\endgroup$
    – Kaya
    Dec 26, 2013 at 18:06
  • $\begingroup$ @Kaya Thanks for the link and I want to know if there is a case where Prim's Algorithm doesn't always yield the correct result $\endgroup$
    – fudu
    Dec 26, 2013 at 18:10
  • $\begingroup$ What conditions do you desire this graph satisfy? By the proof of correctness Prim's algorithm will produce a minimum spanning tree for any graph G which satisfies the hypotheses (i.e. connected, weighted). Do you wish to discard one of these properties? $\endgroup$
    – Kaya
    Dec 26, 2013 at 18:15
  • 1
    $\begingroup$ The proof of correctness' only assumptions are that G is a connected, weighted graph. From these assumptions it then lays out a chain of logical implications (each founded on some other known result in mathematics) which lead to the conclusion that Prim's algorithm applied to G yields the minimum spanning tree of G. Since G was chosen arbitrarily among all connected, weighted graphs this proof asserts that there are no counterexamples within this class. As I understand your question there can be no answer. $\endgroup$
    – Kaya
    Dec 26, 2013 at 18:37
  • 1
    $\begingroup$ One could even ask a stronger question: given a correct algorithm, is it possible to find a counterexample where the algorithm produces a wrong result? The result for that question and your question is NO, it is impossible. $\endgroup$
    – Juho
    Dec 29, 2013 at 12:10

1 Answer 1

1
$\begingroup$

For any un-directed graph G that is connected and weighted Prim's algorithm will produce the MST of the graph. However if the graph is directed this does not hold, as an example consider this directed graph:

╔═╗        ╔═╗        ╔═╗
║ ║---5--->║B║---5--->║ ║
║ ║        ╚═╝        ║ ║
║A║                   ║D║
║ ║        ╔═╗        ║ ║
║ ║---6--->║C║---1--->║ ║
╚═╝        ╚═╝        ╚═╝

Starting with A Prim's algorithm would choose edges (A,B),(B,D),(A,C) total weight of 16. The MST (if it were undirected) however is given by the edges (A,B),(A,C),(C,D) with a total weight of 12.

I should also clarify that directed graphs do not have MSTs (as they are only defined for undirected graphs). The closest notion for directed graphs would be Arborescence and an example of an algorithm which solves this similar question for directed graphs is Edmonds' Algorithm.

$\endgroup$
2
  • 2
    $\begingroup$ This is not just a technicality; this is fundamental. The notion of a MST is not well-defined for a directed graph, so it doesn't even make sense to ask whether applying Prim's algorithm to a directed graph produces a MST. But the original question seems a bit confused, and hopefully the last paragraph will help the original poster a lot. $\endgroup$
    – D.W.
    Dec 26, 2013 at 22:05
  • $\begingroup$ @D.W. Right you are, I edited the question to further emphasize this fact. $\endgroup$
    – Kaya
    Dec 27, 2013 at 1:19

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.