Prim: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(15 intermediate revisions by 2 users not shown)
Line 1: Line 1:
== Pseudocode ==
[[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}}


=== MST-PRIM(''G,w,r'') ===
== General information ==


<code>
'''Algorithmic problem:''' [[Minimum spanning tree]]
MST-PRIM(''G,w,r'')
 
  1  '''for''' each vertex ''u'' &isin; ''V''[''G'']  
'''Prerequisites:'''
  2      '''do''' ''key''[''u''] = &infin;
 
  3                &pi;[''u''] = NIL
'''Type of algorithm:''' loop
  4  ''key''[''r''] = 0
 
  5  ''Q'' = ''V''[''G'']
'''Auxiliary data:'''
  6  '''while''' ''Q'' &ne; &Oslash;
#A key <math>k_v \in \mathbb{R}</math> for each node <math>v \in V</math>.
  7      '''do''' ''u'' = EXTRACT-MIN(''Q'')
#A priority queue <math>Q</math> of nodes. The key of a node <math>v</math> for <math>Q</math> is <math>k_v</math>, the information is one of the edges of <math>G</math> that is [[incident]] to <math>v</math>.
  8                '''for''' each v &isin; ''Adj[u]''
 
  9                      '''do if''' v &isin; ''Q'' and ''w(u,v)'' < ''key''[''v'']
==Abstract view==
10                              '''then''' &pi;[''v''] = ''u''
 
11                                      ''key''[''v''] = ''w(u,v)''
'''Invariant:''' After <math>i \geq 0</math> iterations:
</code>
#There is a node set <math>V_i</math> of size <math>\vert V_i \vert = i+1</math> and an edge set <math>E_i \subseteq E</math> such that <math>E_i</math> solely connects nodes in <math>V_i</math>, and <math>V(V_i,E_i)</math> is a tree.
#There is a minimum spanning tree <math>(V,E'_i)</math> of <math>G</math> such that <math>E_i \subseteq E'_i</math>.
#The key <math>k_v</math> of <math>v \in V \setminus V_i</math> is the minimal length of an edge that connects <math>v</math> with some node in <math>V_i</math> (or <math>K_v = +\infty</math>, if there is no such edge). If <math>v \in Q</math> and <math>K_v < +\infty</math>, this edge is the information associated with <math>v</math> in <math>Q</math>.
Note that, once a node joins <math>V_i</math>, its key will be irrelevant for the rest of the algorithm.
 
'''Variant:''' <math>i</math> increases by <math>1</math>.
 
'''Break condition:''' <math>i = n - 1</math>; then return <math>E_{n-1}</math>.
 
==Induction basis==
 
'''Abstract view:'''
#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>:
##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>.
'''Implementation:''' Obvious.
 
'''Proof:''' Obvious.
 
==Induction step==
 
'''Abstract view:'''
#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>.
#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>k_w := \ell((v,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>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>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>.
 
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.
 
==Complexity==
 
'''Statement:''' <math>\mathcal{O}((n+m) \cdot T(n))</math> in the worst case, where <math>n = \vert V \vert</math> and <math>m = \vert A \vert</math> and <math>T(n)</math> is the asymptotic complexity of the methods of <math>Q</math> .
 
'''Proof:''' In the preprocessing, <math>n - 1</math> nodes are to be inserted in <math>Q</math>, which takes <math>\mathcal{O}(n \cdot T(n))</math> time. Since each node is inserted at most once, all extraction operations take <math>\mathcal{O}(n \cdot T(n))</math> time, too. For each edge, <math>Q</math> has to be rearranged at most once, which results in <math>\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.

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.