Prim: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
(10 intermediate revisions by one other user not shown)
Line 1: Line 1:
[[Category:Minimum spanning tree]]
[[Category:Videos]]
{{#ev:youtube|https://www.youtube.com/watch?v=tGsKpnBBM2U|500|right|Chapters
#[00:00] Einführung
#[01:27] Der Algorithmus von Prim anhand eines Beispiels
#[06:59] Korrektheitsbeweis für den Algorithmus von Prim
#[11:14] Das sieht doch aus wie der Algorithmus von Dijkstra?
#[12:07] Wie lautet die Invariante?
#[12:40] Warum ist der Algorithmus korrekt?
#[13:00] Wie wird die Invariante sichergestellt?
#[13:47] Was ist die asymptotische Komplexität des Algorithhmus?|frame}}
== General information ==
'''Algorithmic problem:''' [[Minimum spanning tree]]
'''Algorithmic problem:''' [[Minimum spanning tree]]


Line 26: Line 40:
#Choose an arbitrary node <math>s \in V</math> and set <math>V_0 := \{s\}</math>.
#Choose an arbitrary node <math>s \in V</math> and set <math>V_0 := \{s\}</math>.
#For each node <math>v \in V \setminus \{s\}</math>:
#For each node <math>v \in V \setminus \{s\}</math>:
##If <math>\{s,v\} \in E</math>, set <math>k_v := \ell(\{s,v\})</math>, otherwise set <math>k_v := + \infty</math>.
##If <math>(s,v) \in E</math>, set <math>k_v := \ell((s,v))</math>, otherwise set <math>k_v := + \infty</math>.
##Insert <math>v</math> with key <math>k_v</math> in <math>Q</math>.
##Insert <math>v</math> with key <math>k_v</math> in <math>Q</math>.
'''Implementation:''' Obvious.
'''Implementation:''' Obvious.
Line 37: Line 51:
#Extract the first node <math>v</math> from <math>Q</math>.
#Extract the first node <math>v</math> from <math>Q</math>.
#Let <math>e</math> denote the edge stored as information for <math>v</math> in <math>Q</math>.
#Let <math>e</math> denote the edge stored as information for <math>v</math> in <math>Q</math>.
#For each <math>w \in V \setminus <math>Insert formula here</math>V_{i-1}</math> such that <math>\{v,w\} \in E</math> and <math>\ell(\{v,w\}) < k_w</math>:
#For each <math>w \in V \setminus V_{i-1}</math> such that <math>(v,w) \in E</math> and <math>\ell((v,w)) < k_w</math>:
##Set <math>\{v,w\}</math> as the new information for <math>w</math> in <math>Q</math>.
##Set <math>(v,w)</math> as the new information for <math>w</math> in <math>Q</math>.
##Set <math>k_w := \ell(\{v,w\})</math>.
##Set <math>k_w := \ell((v,w))</math>.
##Rearrange <math>Q</math> according to the decreased key <math>k_w</math>.
##Rearrange <math>Q</math> according to the decreased key <math>k_w</math>.
#<math>E_i := E_{i-1} \cup \{e\}</math>.
#<math>E_i := E_{i-1} \cup \{e\}</math>.
Line 45: Line 59:
'''Implementation:''' Obvious.
'''Implementation:''' Obvious.


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


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


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

Latest revision as of 09:28, 21 June 2015

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