Prim

From Algowiki
Jump to navigation Jump to search
Chapters
  1. [00:00] Einführung
  2. [01:27] Der Algorithmus von Prim anhand eines Beispiels
  3. [06:59] Korrektheitsbeweis für den Algorithmus von Prim
  4. [11:14] Das sieht doch aus wie der Algorithmus von Dijkstra?
  5. [12:07] Wie lautet die Invariante?
  6. [12:40] Warum ist der Algorithmus korrekt?
  7. [13:00] Wie wird die Invariante sichergestellt?
  8. [13:47] Was ist die asymptotische Komplexität des Algorithhmus?

General information

Algorithmic problem: Minimum spanning tree

Prerequisites:

Type of algorithm: loop

Auxiliary data:

  1. A key kvR for each node vV.
  2. A priority queue Q of nodes. The key of a node v for Q is kv, the information is one of the edges of G that is incident to v.

Abstract view

Invariant: After i0 iterations:

  1. There is a node set Vi of size |Vi|=i+1 and an edge set EiE such that Ei solely connects nodes in Vi, and V(Vi,Ei) is a tree.
  2. There is a minimum spanning tree (V,Ei) of G such that EiEi.
  3. The key kv of vVVi is the minimal length of an edge that connects v with some node in Vi (or Kv=+, if there is no such edge). If vQ and Kv<+, this edge is the information associated with v in Q.

Note that, once a node joins Vi, its key will be irrelevant for the rest of the algorithm.

Variant: i increases by 1.

Break condition: i=n1; then return En1.

Induction basis

Abstract view:

  1. Choose an arbitrary node sV and set V0:={s}.
  2. For each node vV{s}:
    1. If (s,v)E, set kv:=((s,v)), otherwise set kv:=+.
    2. Insert v with key kv in Q.

Implementation: Obvious.

Proof: Obvious.

Induction step

Abstract view:

  1. Extract the first node v from Q.
  2. Let e denote the edge stored as information for v in Q.
  3. For each wVVi1 such that (v,w)E and ((v,w))<kw:
    1. Set (v,w) as the new information for w in Q.
    2. Set kw:=((v,w)).
    3. Rearrange Q according to the decreased key kw.
  4. Ei:=Ei1{e}.
  5. Vi:=Vi1{v}.

Implementation: Obvious.

Correctness: The first and third invariants are obviously maintained, so we will focus on the second invariant. Let uVi1 denote the other endnode of e, so it is e=(u,v).

Since (V,Ei1) is a spanning tree of G, there is exactly one path p in (V,Ei1 connecting u and v. As (V,Ei1) is cycle-free and contains the tree (Vi1,Ei1), p contains exactly one edge e=(v,w)Ei1 such that vVi1 and wVi1. If e=e (and thus p=(e)), the invariant is maintained by Ei:=Ei1. So consider the case that ee.

Note that eQ immediately before the i-th iteration. Therefore, the specific choice of implies (e)(e). So, with Ei:=Ei1{e}{e} we obtain a spanning tree of G whose weight is not larger than that of (V,Ei1), which is minimum by definition.

Complexity

Statement: O((n+m)T(n)) in the worst case, where n=|V| and m=|A| and T(n) is the asymptotic complexity of the methods of Q .

Proof: In the preprocessing, n1 nodes are to be inserted in Q, which takes O(nT(n)) time. Since each node is inserted at most once, all extraction operations take O(nT(n)) time, too. For each edge, Q has to be rearranged at most once, which results in O(mT(n)) time. Clearly, all other operations of the preprocessing and the main loop are dominated by these bounds as well.