Prim

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?

Algorithmic problem: Minimum spanning tree

Prerequisites:

Type of algorithm: loop

Auxiliary data:

1. A key [math]\displaystyle{ k_v \in \mathbb{R} }[/math] for each node [math]\displaystyle{ v \in V }[/math].
2. A priority queue [math]\displaystyle{ Q }[/math] of nodes. The key of a node [math]\displaystyle{ v }[/math] for [math]\displaystyle{ Q }[/math] is [math]\displaystyle{ k_v }[/math], the information is one of the edges of [math]\displaystyle{ G }[/math] that is incident to [math]\displaystyle{ v }[/math].

Abstract view

Invariant: After [math]\displaystyle{ i \geq 0 }[/math] iterations:

1. There is a node set [math]\displaystyle{ V_i }[/math] of size [math]\displaystyle{ \vert V_i \vert = i+1 }[/math] and an edge set [math]\displaystyle{ E_i \subseteq E }[/math] such that [math]\displaystyle{ E_i }[/math] solely connects nodes in [math]\displaystyle{ V_i }[/math], and [math]\displaystyle{ V(V_i,E_i) }[/math] is a tree.
2. There is a minimum spanning tree [math]\displaystyle{ (V,E'_i) }[/math] of [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ E_i \subseteq E'_i }[/math].
3. The key [math]\displaystyle{ k_v }[/math] of [math]\displaystyle{ v \in V \setminus V_i }[/math] is the minimal length of an edge that connects [math]\displaystyle{ v }[/math] with some node in [math]\displaystyle{ V_i }[/math] (or [math]\displaystyle{ K_v = +\infty }[/math], if there is no such edge). If [math]\displaystyle{ v \in Q }[/math] and [math]\displaystyle{ K_v \lt +\infty }[/math], this edge is the information associated with [math]\displaystyle{ v }[/math] in [math]\displaystyle{ Q }[/math].

Note that, once a node joins [math]\displaystyle{ V_i }[/math], its key will be irrelevant for the rest of the algorithm.

Variant: [math]\displaystyle{ i }[/math] increases by [math]\displaystyle{ 1 }[/math].

Break condition: [math]\displaystyle{ i = n - 1 }[/math]; then return [math]\displaystyle{ E_{n-1} }[/math].

Induction basis

Abstract view:

1. Choose an arbitrary node [math]\displaystyle{ s \in V }[/math] and set [math]\displaystyle{ V_0 := \{s\} }[/math].
2. For each node [math]\displaystyle{ v \in V \setminus \{s\} }[/math]:
   1. If [math]\displaystyle{ (s,v) \in E }[/math], set [math]\displaystyle{ k_v := \ell((s,v)) }[/math], otherwise set [math]\displaystyle{ k_v := + \infty }[/math].
   2. Insert [math]\displaystyle{ v }[/math] with key [math]\displaystyle{ k_v }[/math] in [math]\displaystyle{ Q }[/math].

Implementation: Obvious.

Proof: Obvious.

Induction step

Abstract view:

1. Extract the first node [math]\displaystyle{ v }[/math] from [math]\displaystyle{ Q }[/math].
2. Let [math]\displaystyle{ e }[/math] denote the edge stored as information for [math]\displaystyle{ v }[/math] in [math]\displaystyle{ Q }[/math].
3. For each [math]\displaystyle{ w \in V \setminus V_{i-1} }[/math] such that [math]\displaystyle{ (v,w) \in E }[/math] and [math]\displaystyle{ \ell((v,w)) \lt k_w }[/math]:
   1. Set [math]\displaystyle{ (v,w) }[/math] as the new information for [math]\displaystyle{ w }[/math] in [math]\displaystyle{ Q }[/math].
   2. Set [math]\displaystyle{ k_w := \ell((v,w)) }[/math].
   3. Rearrange [math]\displaystyle{ Q }[/math] according to the decreased key [math]\displaystyle{ k_w }[/math].
4. [math]\displaystyle{ E_i := E_{i-1} \cup \{e\} }[/math].
5. [math]\displaystyle{ V_i := V_{i-1} \cup \{v\} }[/math].

Implementation: Obvious.

Correctness: The first and third invariants are obviously maintained, so we will focus on the second invariant. Let [math]\displaystyle{ u \in V_{i-1} }[/math] denote the other endnode of [math]\displaystyle{ e }[/math], so it is [math]\displaystyle{ e = (u,v) }[/math].

Since [math]\displaystyle{ (V,E'_{i-1}) }[/math] is a spanning tree of [math]\displaystyle{ G }[/math], there is exactly one path [math]\displaystyle{ p }[/math] in [math]\displaystyle{ (V,E'_{i-1} }[/math] connecting [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math]. As [math]\displaystyle{ (V,E'_{i-1}) }[/math] is cycle-free and contains the tree [math]\displaystyle{ (V_{i-1},E_{i-1}) }[/math], [math]\displaystyle{ p }[/math] contains exactly one edge [math]\displaystyle{ e' = (v',w') \in E'_{i-1} }[/math] such that [math]\displaystyle{ v' \in V_{i-1} }[/math] and [math]\displaystyle{ w' \notin V_{i-1} }[/math]. If [math]\displaystyle{ e' = e }[/math] (and thus [math]\displaystyle{ p = (e) }[/math]), the invariant is maintained by [math]\displaystyle{ E'_i := E'_{i-1} }[/math]. So consider the case that [math]\displaystyle{ e' \neq e }[/math].

Note that [math]\displaystyle{ e' \in Q }[/math] immediately before the [math]\displaystyle{ i }[/math]-th iteration. Therefore, the specific choice of implies [math]\displaystyle{ \ell(e') \geq \ell(e) }[/math]. So, with [math]\displaystyle{ E'_i := E'_{i-1} \setminus \{e'\} \cup \{e\} }[/math] we obtain a spanning tree of [math]\displaystyle{ G }[/math] whose weight is not larger than that of [math]\displaystyle{ (V,E'_{i-1}) }[/math], which is minimum by definition.

Complexity

Statement: [math]\displaystyle{ \mathcal{O}((n+m) \cdot T(n)) }[/math] in the worst case, where [math]\displaystyle{ n = \vert V \vert }[/math] and [math]\displaystyle{ m = \vert A \vert }[/math] and [math]\displaystyle{ T(n) }[/math] is the asymptotic complexity of the methods of [math]\displaystyle{ Q }[/math] .

Proof: In the preprocessing, [math]\displaystyle{ n - 1 }[/math] nodes are to be inserted in [math]\displaystyle{ Q }[/math], which takes [math]\displaystyle{ \mathcal{O}(n \cdot T(n)) }[/math] time. Since each node is inserted at most once, all extraction operations take [math]\displaystyle{ \mathcal{O}(n \cdot T(n)) }[/math] time, too. For each edge, [math]\displaystyle{ Q }[/math] has to be rearranged at most once, which results in [math]\displaystyle{ \mathcal{O}(m \cdot T(n)) }[/math] time. Clearly, all other operations of the preprocessing and the main loop are dominated by these bounds as well.