Algowiki - User contributions [en]

Insertion sort

2023-02-20T09:11:38Z

Luedecke: Created page with "Content not available due to incorrectness and not relevant for Karsten Weihe's lectures."

Content not available due to incorrectness and not relevant for Karsten Weihe's lectures.

Floyd-Warshall

2022-05-24T09:28:24Z

Luedecke:

== Abstract View ==

'''Algorithmic problem:''' [[All pairs shortest paths]]

'''Prerequisites:''' None

'''Type of algorithm:''' loop

'''Auxilliary data:'''
# A constant representing the number of node: <math>n = |V|</math>
# A real-valued <math>(n \times n)</math> matrix <math>M</math>
# An ordering of all nodes, that is, <math>V = \{u_1, \ldots ,u_n\}</math>

'''Notation:'''
On this page, <math>M^i</math> refers to the contents of <math>M</math> after <math>i\geq 0</math> iterations.

'''Invariant:''' After <math>i \ge 0</math> iterations, for <math>v,w \in V</math>, <math>M(v,w)</math> is the length of a shortest <math>(v,w)</math>-path subject to the constraint that all [[internal nodes]] of the path belong to <math>\{u_1, \ldots , u_i\}</math>.

'''Variant:''' <math>i</math> increases by <math>1</math>.

'''Break condition:''' It is <math>i=n</math>

== Induction basis ==
'''Abstract view:''' For all <math>v,w \in V</math> we set
# <math>M(v,v):=0, \forall v \in V</math>
# <math>M(v,w):=l(v,w), (v,w) \in A</math>
# <math>M(v,w):= +\infty</math>, otherwise

'''Implementation:''' Obvious.

'''Proof:''' Nothing to show.

== Induction step ==
'''Abstract view:''' Bring <math>v_i</math> into the game.

'''Implementation:'''
For all <math>v,w\in V</math>, set <math>M^{i+1}(v,w):=\min\{M^i(v,w),M^i(v,u_i)+M^i(u_i,w)\}</math>.

'''Correctness:''' Let <math>p</math> denote a shoortest <math>(v,w</math>-path subject to the constraint that all [[Basic graph definitions#Paths|internal nodes]] are taken from <math>\{u_1, \ldots, u_n \}</math>.
# If <math>p</math> does not contain <math>u_i</math>, <math>p</math> is even a shortest <math>(v,w)</math>-path such that all internal nodes are taken from <math>\{u_1, \ldots , u_{i-1} \}</math>. In this case, the induction hypothesis implies that the value of <math>M(v,w)</math> immediately before the i-th iteration equals the length of <math>p</math>. Clearly, the i-th iteration does not change the value of <math>M(v,w)</math> in this case.
# On the other hand, suppose <math>p</math> does contain <math>u_i</math>. Due to the [[basics of shortest paths#Subpath property of shortest paths|prefix property]], the segment of <math>p</math> from <math>v</math> to <math>u_i</math> and from <math>u_i</math> to <math>w</math> are a shortest <math>(v,u_i)</math>-path and a shortest <math>(u_i,w)</math>-path, respectively, subject to the constraint that all internal nodes are from <math>\{u_1, \ldots , u_{i-1} \}</math>. The induction hypothesis implies that tehese lengths equal the values <math>M(v,u_i)</math> and <math>M(u_i, w)</math>, respectively.

== Complexity ==
'''Statement:''' <math>\mathcal{O}(n^3)</math>

'''Proof:''' The overall loop has <math>n</math> iterations. In each iteration, we update all <math>n^2</math> matrix entities. Each update requires a constant number of steps.

Dijkstra

2021-01-14T08:35:20Z

Luedecke:

{{#ev:youtube|https://www.youtube.com/watch?v=6nSc8ojXZ1A|500|right|Chapters
#[00:00] Einführung
#[05:33] Ändern sich die Pfade stark in jeder Iteration?
#[06:08] Auf was für Strukturen arbeiten wir eigentlich?
#[07:26] Distanzen und kürzeste Pfade
#[10:59] Varianten des Kürzeste-Pfade-Problems
#[14:00] Dijkstra implementiert
#[16:00] Wieso funktioniert dieser Algorithmus, warum ist er korrekt?
#[21:28] Was gibt es zum Preprocessing bzw. Induktionsanfang zu sagen?
#[21:57] Was ist in der Queue?
#[22:15] Was wissen wir über die erledigten Knoten?
#[23:00] Und was wissen wir über die unerledigten Knoten?
#[23:49] Und was ist mit der asymptotischen Komplexität?
|frame}}
[[Category:Videos]]
[[Category:Graph Algorithms]]
[[Category:All Pairs Shortest Paths]]
[[Category:Shortest Paths Problems]]
[[Category:Checkup]]

== General information ==

'''Algorithmic problem:''' [[Single source shortest paths]]

'''Prerequisities:''' For all <math>a\in A</math>, it is <math>l(a) \geq 0</math>.

'''Type of algortihm:''' loop

'''Auxiliary data:'''
# A temporary '''distance value''' <math>\delta(v) \in \mathbb{R}</math> for each node <math>v \in V</math>. At termination, it is <math>\delta(v) = \Delta(v)</math> for all <math>v \in V</math> where <math>\Delta(v)</math> is the shortest <math>(s,v)</math>-path.
# A [[bounded priority queue]] <math>Q</math> of size <math>|V|-1</math>, which contains nodes from <math>V</math> and takes their <math>\delta</math>-values as keys. The node with minimal key is returned.

== Abstract view ==

'''Invariant:''' After <math>i \geq 0</math> iterations:
# <math>Q</math> contains all nodes of <math>V</math> except <math>s</math> and <math>i</math> further nodes.
# For the nodes <math>v \in V</math> not in <math>Q</math>, it is <math>\delta(v) = \Delta(v)</math>.
# For the nodes <math>v \in V</math> in <math>Q</math>, <math>\delta(v)</math> is the length of a shortest <math>(s,v)</math>-path that solely contains nodes not in <math>Q</math> (except for <math>v</math> itself, of course). As usual, this means <math>\delta(v) = +\infty</math> if there is no such path.

In particular, it is <math>\delta(v) \geq \Delta(v)</math> for each node <math>v \in V</math>.

'''Variant:''' <math>i</math> increases by <math>1</math>.

'''Break condition:'''
* <math>Q = \emptyset</math>, which means that all nodes are reachable from <math>s</math> and have been processed;
* otherwise, if <math>\delta(v) = +\infty</math> for the next node <math>v</math> of <math>Q</math>, which means that <math>\delta(v) = + \infty</math> for '''every''' node in <math>Q</math> and hence none of the nodes in <math>Q</math> is reachable from <math>s</math>.

== Induction basis ==
=== Abstract view: ===
# All nodes of <math>V</math> except <math>s</math> have to be members of <math>Q</math>.
# Root <math>s</math> must have correct distance <math>\Delta(s) = 0</math>.
# The other nodes must meet Invariant #3.

=== Implementation: ===
# <math>\delta(s) := 0</math>;
# For all <math>a = (s,v) \in A</math>, set <math>\delta(v) := l(a)</math>.
# For all <math>v \in V\setminus\{s\}</math> with <math>(s,v) \notin A</math> set <math>\delta(v) := +\infty</math>.
# Insert all nodes in <math>V\setminus\{s\}</math> into <math>Q</math>.

=== Proof: ===
Obvious.

== Induction step ==

=== Abstract view: ===
One node is extracted from <math>Q</math>, and the distance values of the endnodes of its outgoing arcs are updated to meet Invariant #3.

=== Implementation: ===
# Extract the next node <math>v</math> from <math>Q</math>.
# For each outgoing arc <math>a = (v,w) \in A</math> such that <math>w \in Q</math>, set <math>\delta(w) := min\{\delta(w), \delta(v) + l(a)\}</math>.

=== Correctness: ===
The first invariant is trivially maintained. So we will focus on the second and third invariants.<br>
Consider the moment immediately before the <math>i</math>-iteration. The core of the proof is to show that <math>\delta(v) = \Delta(v)</math> hold at that moment (and hence forever). For a contradiction, suppose there is an <math>(s,v)</math>-path <math>p</math> whose length is strictly less than <math>\delta(v)</math>. The third invariant implies that <math>p</math> has nodes in <math>Q</math> beside <math>v</math>. Let <math>u</math> denote the first such node on <math>p</math>. Then none of the nodes on the subpath of <math>p</math> from <math>s</math> to <math>u</math> belonged to <math>Q</math> at that moment (except for <math>u</math> itself, of course). Due to the [[[[basics of shortest paths#Subpath property of shortest paths|prefix property]], this subpath is a shortest <math>(s,u)</math>-path, so Invariant #3 implies <math>\delta(u) = \Delta(u)</math>. On the other hand, the specific choice of <math>v</math> implies <math>\delta(u) \geq \delta(v)</math>. In summary, the subpath of <math>p</math> from <math>s</math> to <math>u</math> is not shorter than <math>\delta(v)</math>. To obtain <math>l(p) < \delta(v)</math>, the subpath of <math>p</math> from <math>u</math> to <math>v</math> must have negative total length, which contradicts the prerequisite <math>l \geq 0</math>.<br>
Now we know <math>\delta(v) = \Delta(v)</math>. Therefore, <math>v</math> fulfills the statement of the second invariant after the <math>i</math>-th iteration. Of course, the second invariant is not violated by any other node either, and is thus maintained.<br>
For a node <math>w \in V</math> let <math>P_i (w)</math> denote the set of all <math>(s,w)</math>-paths such that no node (except for <math>w</math> itself) is in <math>Q</math> immediately after the <math>i</math>-th iteration. In particular, the statement of the third invariant means that <math>\delta(w)</math> is the length of a shortest path in <math>P_i (w)</math>. The induction hypothesis says that <math>\delta(w)</math> is the minimum length of all <math>(s,w)</math>-paths in <math>P_{i-1} (w)</math>. The difference <math>P_i (w) \setminus P_{i-1} (w)</math> consists of all <math>(s,w)</math>-paths such that <math>(v,w)</math> is the last arc and all nodes except for <math>v</math> and <math>w</math> were not in <math>Q</math> anymore immediately before the current iteration. Therefore, the second step of the iteration incorporates <math>P_i (w) \setminus P_{i-1} (w)</math> in the computation of <math>\delta(w)</math> appropriately to maintain Invaraint #3.

== Complexity ==

'''Statement:''' The worst-case complexity is in <math>O(T(n)\cdot(n+m))</math>, where <math>n = |V|</math> and <math>m = |A|</math>, and <math>T(n)</math> is the worst-case complexity for extraction/inserting nodes in <math>Q</math>.

'''Proof:''' Each node is inserted in and extracted from <math>Q</math> at most once, respectively, which gives <math>O(T(n) \cdot n)</math> in total. Also, each arc <math>(v,w) \in A</math> is touched at most once, namely
* in the initialization if <math>v = s</math>,
* when <math>v</math> is extracted from <math>Q</math> otherwise.
Therefore, all decrease-key operations require <math>O(T(n) \cdot m)</math> in total.

== Heuristic speed-up techniques ==
# We do not need to insert all nodes except for <math>s</math> in <math>Q</math>. In fact, it suffices to initially insert the endnodes of the outgoing arcs of <math>s</math> and, during an iteration, to insert the nodes of the outgoing arcs of the node that is being extracted from <math>Q</math>. In a sense, the nodes of <math>Q</math> then constitute the "frontierline" of the algorithm. We choose another variant on Dijkstra's algorithm mainly for simplicity of presentation.
# Clearly, Dijkstra's algorithm also solves the single-source single-target case. In this case, Dijkstra may safely terminate once <math>t</math> has been extracted from <math>Q</math>. In fact, the loop invariant implies <math>\delta(t) = \Delta(t)</math> from then on. This variant on Dijkstra's algorithm is sometimes called the '''early termination variant'''.[[File:Dijkstrabidirectional.png|350px|thumb|right|advantage of a bidirectional search]]
# In the single-source single-target case, two searches may be applied simultaneously: one from <math>s</math> on <math>G</math>, the other one from <math>t</math> on the [[Basic graph definitions#Transpose of a graph|transpose]] of <math>G</math>. This variant is called '''bidirectional search'''. It terminates once one node has been seen by both searches. Then either the concatenation of the paths to this node from both searches is a shortest <math>(s,t)</math>-path, or such a path may be found among the paths of the following kind: There is an arc <math>(v,w)\in A</math> such that <math>v</math> has been seen in the forward search from the source and <math>w</math> has been seen in the backward search from <math>t</math>.
# In a scenario where we perform a large number of searches on the same graph and arc lengths, we do not need to touch the whole graph in each search:
## We change the algorithm as suggested by the first point: only keep the "frontierline" in <math>Q</math>.
## We also change the algorithm as suggested by the second point: terminate once <math>t</math> is processed.
## To avoid touching all nodes for initializing the <math>\delta</math>-values, we maintain sort of a '''version counter''', or '''time stamp''', for each node, which holds the ID of the last search that met this node. Whenever a node is met in a search and the nodes version counter does not equal the ID of the current search, the distance value of this node is regarded as <math>+ \infty</math> (no matter what its current value is).[[File:Dijkstragoaldirected.png|350px|thumb|right|the length of a non-goal-directed arc grows, the length of a neutral arc stays the same and the length of the goal-directed arc shriks]]
# The early termination variant may be modified as follows: For [[Basics of shortest paths#(Admissible) node potentials|admissible node potentials]] <math>h:V \to \mathbb{R}</math>, replace length <math>\ell</math> by <math>\ell_h</math> where <math>\ell_h(a) := \ell(a) + h(w) - h(v)</math> for each <math>a = (v,w) \in A</math>. This variant is usually called '''goal-directed search'''. The heuristic idea is that we (hopefully) reach <math> t</math> earlier because the arcs that roughly point towards <math>t</math> are shortened, and the arcs the roughly point in a direction away from <math>t</math> are lengthened.

Main Page

2020-11-30T15:13:46Z

Luedecke:

=== Notations ===
* [[Big O notation]]
* [[L' Hospital]]
* [[Master theorem]]
* [[Asymptotic comparison of functions]]

=== Problems ===
* [[Matchings in graphs#Cardinality-maximal matching|Maximum matching problem]]
* [[Max-Flow Problems]]
* [[Min-Cost Flow Problems]]
* [[Shortest Paths Problems]]
** [[All pairs shortest paths]]
*** [[Floyd-Warshall]]
*** [[Bellman-Ford]] (DONE)
*** [[Shortest paths by repeated squaring]] (variant of Bellman-Ford)
** [[Single source shortest paths]]
*** [[Dijkstra]]
** [[Single source single target shortest paths]]
*** [[A*]] (Empty in old wiki)
* [[Maximum spanning forest]]
* [[Problems on Sequences]]
** [[Basic Problems on Sequences]]
*** [[Find an element in a sequence]] (DONE)
*** [[Insert an element in a sequence]] (Empty in old wiki?!)
*** [[Median]] (DONE)
*** [[Merging two sorted sequences]] (DONE)
** [[Pattern Matching]]
*** [[One-dimensional string matching]] (DONE)
*** [[String matching]] (DONE)
** [[Sorting]]
*** [[Sorting based on pairwise comparison]] (DONE)
*** [[Sorting Sequences of Strings]] (DONE)

=== Coding Basics ===
* [[Inheritance]]
* [[Generics]]
* [[Collections]]
** [[Iterator]]
** [[Comparator]]

=== String Matching Algorithms ===
* [[Simple string matching algorithm]] (DONE)
* [[String matching based on finite automaton]] (DONE)

=== Sorting Algorithms ===
* [[Bubble]]
* [[Insertion sort]]
* [[Quicksort]]
* [[Bubblesort]]
* [[Mergesort]]
* [[Bucketsort]]
* [[Selection sort]]
* [[Bogosort]]

=== Search Algorithms ===
* [[Binary search]]

=== Auxillary Algorithms ===
* [[Pivot partitioning by scanning]]

=== Manipulation ===
* [[Array list: find]]
* [[Array list: find at position]]
* [[Array list: insert at head]]
* [[Array list: insert at position]]
* [[Array list: number]]
* [[Array list: remove]]
* [[Doubly-linked list: insert at position]]
* [[Doubly-linked list: insert at tail]]
* [[Doubly-linked list: remove]]
* [[Find element in sequence iteratively]]
* [[Find element in sequence recursively]]
* [[Hashtable: find]]
* [[Hashtable: insert]]

=== Tree Algorithms ===
* [[Depth-first search]]
* [[Breadth-first search]]
* [[B-tree: find]]
* [[B-tree: minimum]]
* [[B-tree: maximum]]
* [[B-tree: insert]]
* [[B-tree: insert and rearrange]]
* [[B-tree: merge two siblings]]
* [[B-tree: remove]]
* [[B-tree: shift key to sibling]]
* [[B-tree: split]]
* [[Binary search tree: find]]
* [[Binary search tree: minimum]]
* [[Binary search tree: maximum]]
* [[Binary search tree: insert]]
* [[Binary search tree: remove]]
* [[Binary search tree: remove node]]
* [[Binary search tree: traverse]]

=== Graph Theory ===
* [[Directed graph]]
* [[Bipartite graph|Bipartite graph]] (DONE)
* [[k-partite graph]]
* [[Negative paths]]

=== Graph Algorithms ===
* [[Dijkstra]]
* [[Kruskal]]
* [[Prim]]
* [[Bellman-Ford]] (DONE)
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]
* [[Union-find with disjoint trees: find]]
* [[Union-find with lists: unite]]
* [[Max-flow min-cut]]

=== Flow Algorithms ===
* [[Ford-Fulkerson]]
* [[Edmonds-Karp]]

=== Abstract Data Structures ===
*[[Network Structures]]
**[[Graph]]
**[[Tree]]
*[[Sequence]]
**[[Sorted sequence]]
**[[Bounded priority queue]]
**[[Linear sequence]]
**[[Priority queue]]
**[[Sorted sequence]]
=== Implementations of Abstract Data Structures ===
* [[Linked list]]
* [[Array list]]
* [[Binary search tree]]
* [[Doubly-linked list]]
* [[Heap as array]] (DONE (Heap as Array))
* [[Hashtable]]
* [[Multi-way search tree]]
* [[Red-black tree]]
* [[B-tree]]

=== ??? ===
* [[Min-Max Heaps]]
* [[First In - First Out]]
* [[First In - Last Out]]
* [[Directed Tree]]
* [[Decision Tree]]

=== Other ===
* [[Model computer]]

Main Page

2020-11-30T15:13:22Z

Luedecke:

== News ==
* The http://wiki.algo.informatik.tu-darmstadt.de domain will forward to this page from 13th October.
* The old wiki will be reachable at http://huffmann.algo.informatik.tu-darmstadt.de/wiki/
* <math>LaTeX</math> [http://www.mediawiki.org/wiki/Manual:Math available now!]
* ToDo List added
* Every content has to be in English!
* [http://www.mediawiki.org/wiki/Extension:SyntaxHighlight_GeSHi Syntaxhighlight]

== Rules ==
* Add finalized reconstructions of the old Wiki to Category:Checkup.
* Don't add any non-Weihe content until the reconstructions isn't finished.
* Keep your active reconstructing Pages in "Division of labor" section up to date!

'''Look here for short/uncomplete Pages''' [[Special:ShortPages]]

== To Do ==
=== Notations ===
* [[Big O notation]]
* [[L' Hospital]]
* [[Master theorem]]
* [[Asymptotic comparison of functions]]

=== Problems ===
* [[Matchings in graphs#Cardinality-maximal matching|Maximum matching problem]]
* [[Max-Flow Problems]]
* [[Min-Cost Flow Problems]]
* [[Shortest Paths Problems]]
** [[All pairs shortest paths]]
*** [[Floyd-Warshall]]
*** [[Bellman-Ford]] (DONE)
*** [[Shortest paths by repeated squaring]] (variant of Bellman-Ford)
** [[Single source shortest paths]]
*** [[Dijkstra]]
** [[Single source single target shortest paths]]
*** [[A*]] (Empty in old wiki)
* [[Maximum spanning forest]]
* [[Problems on Sequences]]
** [[Basic Problems on Sequences]]
*** [[Find an element in a sequence]] (DONE)
*** [[Insert an element in a sequence]] (Empty in old wiki?!)
*** [[Median]] (DONE)
*** [[Merging two sorted sequences]] (DONE)
** [[Pattern Matching]]
*** [[One-dimensional string matching]] (DONE)
*** [[String matching]] (DONE)
** [[Sorting]]
*** [[Sorting based on pairwise comparison]] (DONE)
*** [[Sorting Sequences of Strings]] (DONE)

=== Coding Basics ===
* [[Inheritance]]
* [[Generics]]
* [[Collections]]
** [[Iterator]]
** [[Comparator]]

=== String Matching Algorithms ===
* [[Simple string matching algorithm]] (DONE)
* [[String matching based on finite automaton]] (DONE)

=== Sorting Algorithms ===
* [[Bubble]]
* [[Insertion sort]]
* [[Quicksort]]
* [[Bubblesort]]
* [[Mergesort]]
* [[Bucketsort]]
* [[Selection sort]]
* [[Bogosort]]

=== Search Algorithms ===
* [[Binary search]]

=== Auxillary Algorithms ===
* [[Pivot partitioning by scanning]]

=== Manipulation ===
* [[Array list: find]]
* [[Array list: find at position]]
* [[Array list: insert at head]]
* [[Array list: insert at position]]
* [[Array list: number]]
* [[Array list: remove]]
* [[Doubly-linked list: insert at position]]
* [[Doubly-linked list: insert at tail]]
* [[Doubly-linked list: remove]]
* [[Find element in sequence iteratively]]
* [[Find element in sequence recursively]]
* [[Hashtable: find]]
* [[Hashtable: insert]]

=== Tree Algorithms ===
* [[Depth-first search]]
* [[Breadth-first search]]
* [[B-tree: find]]
* [[B-tree: minimum]]
* [[B-tree: maximum]]
* [[B-tree: insert]]
* [[B-tree: insert and rearrange]]
* [[B-tree: merge two siblings]]
* [[B-tree: remove]]
* [[B-tree: shift key to sibling]]
* [[B-tree: split]]
* [[Binary search tree: find]]
* [[Binary search tree: minimum]]
* [[Binary search tree: maximum]]
* [[Binary search tree: insert]]
* [[Binary search tree: remove]]
* [[Binary search tree: remove node]]
* [[Binary search tree: traverse]]

=== Graph Theory ===
* [[Directed graph]]
* [[Bipartite graph|Bipartite graph]] (DONE)
* [[k-partite graph]]
* [[Negative paths]]

=== Graph Algorithms ===
* [[Dijkstra]]
* [[Kruskal]]
* [[Prim]]
* [[Bellman-Ford]] (DONE)
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]
* [[Union-find with disjoint trees: find]]
* [[Union-find with lists: unite]]
* [[Max-flow min-cut]]

=== Flow Algorithms ===
* [[Ford-Fulkerson]]
* [[Edmonds-Karp]]

=== Abstract Data Structures ===
*[[Network Structures]]
**[[Graph]]
**[[Tree]]
*[[Sequence]]
**[[Sorted sequence]]
**[[Bounded priority queue]]
**[[Linear sequence]]
**[[Priority queue]]
**[[Sorted sequence]]
=== Implementations of Abstract Data Structures ===
* [[Linked list]]
* [[Array list]]
* [[Binary search tree]]
* [[Doubly-linked list]]
* [[Heap as array]] (DONE (Heap as Array))
* [[Hashtable]]
* [[Multi-way search tree]]
* [[Red-black tree]]
* [[B-tree]]

=== ??? ===
* [[Min-Max Heaps]]
* [[First In - First Out]]
* [[First In - Last Out]]
* [[Directed Tree]]
* [[Decision Tree]]

=== Other ===
* [[Model computer]]

Lecture: Efficient Graph Algorithms

2016-02-13T09:07:39Z

Luedecke: /* Lecture recording 15 */

=Lecture recording 1=
{{#ev:youtube|https://www.youtube.com/watch?v=nw5hkRdrdb8|500|right|
|frame}}
<gallery widths=250px>
File:V1 dial 01.jpg|dial 01
</gallery>
=Lecture recording 2=
{{#ev:youtube|https://www.youtube.com/watch?v=Evt8f8kQPiY|500|right|
|frame}}
<gallery widths="250px">
File:V2 Dijkstra bidirectional Idee.jpg|Dijkstra bidirectional Idee
File:V2 Dijkstra bidirectional Korrektheit.jpg|Dijkstra bidirectional Korrektheit
File:V2 Dijkstra goaloriented Details.jpg|Dijkstra goaloriented Details
File:V2 Dijkstra goaloriented Idee.jpg|Dijkstra goaloriented Idee
File:V2 Dijkstra goaloriented Korrektheit.jpg|Dijkstra goaloriented Korrektheit
</gallery>
=Lecture recording 3=
{{#ev:youtube|https://www.youtube.com/watch?v=Lbnwwl93mHs|500|right|
|frame}}
<gallery widths="250px">
File:V3 BFS Queue.jpg|BFS Queue
File:V3 DFS lax-kleinst.jpg|DFS lax-kleinst
File:V3 DFS lexikographische Knotenreihung.jpg|DFS lexikographische Knotenreihung
File:V3 DFS nichtlexikographische Ausgabereihung.jpg|nichtlexikographische Ausgabereihung
File:V3 DFS Rueckwaertsgehen.jpg|DFS Rueckwaertsgehen
File:V3 Murmelbeweis.jpg|Murmelbeweis
</gallery>
=Lecture recording 4=
{{#ev:youtube|https://www.youtube.com/watch?v=nlIh-hR4T9M|500|right|
|frame}}
<gallery widths="250px">
File:V4 starke Zusammenhangskomponenten.jpg|starke Zusammenhangskomponenten
</gallery>
=Lecture recording 5=
{{#ev:youtube|https://www.youtube.com/watch?v=SJWdFA-b53E|500|right|
|frame}}
<gallery widths="250px">
File:V5 Artikulationspunkt.jpg|Artikulationspunkt
File:V5 Bruecke.jpg|Bruecke
File:V5 DFS 2-fache Zshkomp 1.jpg|DFS 2-fache Zshkomp 1
File:V5 DFS 2-fache Zshkomp 2.jpg|DFS 2-fache Zshkomp 2
File:V5 DFS 2-fache Zshkomp 3.jpg|DFS 2-fache Zshkomp 3
File:V5 DFS 2-fache Zshkomp 4.jpg|DFS 2-fache Zshkomp 4
File:V5 DFS 2-fache Zshkomp 5.jpg|DFS 2-fache Zshkomp 5
File:V5 Euler-Algo schematisch.jpg|Euler-Algo schematisch
File:V5 Haus vom Nikolaus 1.jpg|Haus vom Nikolaus 1
File:V5 Haus vom Nikolaus 2.jpg|Haus vom Nikolaus 2
File:V5 Haus vom Nikolaus 3.jpg|Haus vom Nikolaus 3
</gallery>
=Lecture recording 6=
{{#ev:youtube|https://www.youtube.com/watch?v=7VHBczAZ1tU|500|right|
|frame}}
<gallery widths="250px">
File:V6 Branching Terminologie.jpg|Branching Terminologie
File:V6 Branching Zykelschrumpfung.jpg|Branching Zykelschrumpfung
File:V6 Euler-Algo Beweis.jpg|Euler-Algo Beweis
File:V6 max-flow multi-source multi-target.jpg|max-flow multi-source multi-target
</gallery>
=Lecture recording 7=
{{#ev:youtube|https://www.youtube.com/watch?v=TtAXbP49VJI|500|right|
|frame}}
<gallery widths="250px">
File:V7 Branching Beweis 1.jpg|Branching Beweis 1
File:V7 Branching Beweis 2.jpg|Branching Beweis 2
File:V7 Branching falsches Beispiel.jpg|Branching falsches Beispiel
File:V7_branching_Beitrag_Hoehn.pdf|Branching Beitrag Hoehn
</gallery>
=Lecture recording 8=
{{#ev:youtube|https://www.youtube.com/watch?v=BZIZTig1fKc|500|right|
|frame}}
<gallery widths="250px">
File:V8 anti-symmetric.jpg|anti-symmetric
File:V8 augmenting path.jpg|augmenting path
File:V8 augmenting at a node.jpg|V8 augmenting at a node
File:V8 Cut 1.jpg|Cut 1
File:V8 Cut 2.jpg|Cut 2
File:V8 Cut 3.jpg|Cut 3
File:V8 neuer augmentierender Pfad Bsp.jpg|neuer augmentierender Pfad Bsp
File:V8 neuer augmentierender Pfad einfach.jpg|neuer augmentierender Pfad einfach
</gallery>

=Lecture recording 9=
{{#ev:youtube|https://www.youtube.com/watch?v=eUGnz-yfPco|500|right|
|frame}}
<gallery widths="250px">
File:V9 Ahuha-Orlin Beweis.jpg|Ahuha-Orlin Beweis
File:V9 Complexity Edmonds-Karp.jpg|Complexity Edmonds-Karp
File:V9 neuer augmentierender Pfad komplex.jpg|neuer augmentierender Pfad komplex
File:V9 residual network 1.jpg|residual network 1
File:V9 residual network 2.jpg|residual network 2
</gallery>
=Lecture recording 10=
{{#ev:youtube|https://www.youtube.com/watch?v=SaPIhRYg5Q4|500|right|
|frame}}
<gallery widths="250px">
File:V10 three indians.jpg|three indians
File:V10 valid distance labeling.jpg|valid distance labeling
</gallery>
=Lecture recording 11=
{{#ev:youtube|https://www.youtube.com/watch?v=o9RcytmMCZs|500|right|
|frame}}
<gallery widths="250px">
File:V11 saturierter Schnitt.jpg|saturierter Schnitt
</gallery>
=Lecture recording 12=
{{#ev:youtube|https://www.youtube.com/watch?v=aqen34eNfs8|500|right|
|frame}}
<gallery widths="250px">
File:V12 negative Kostenfaktoren Beispiel.jpg|negative Kostenfaktoren Beispiel
File:V12 negative Kostenfaktoren konzeptionell.jpg|negative Kostenfaktoren konzeptionell
File:V12 negative Zykel Rechnung.jpg|negative Zykel Rechnung
File:V12 negativer Zykel Skizze.jpg|negativer Zykel Skizze
</gallery>

=Lecture recording 13=
{{#ev:youtube|https://www.youtube.com/watch?v=HAQwxvxVbPw|500|right|
|frame}}
<gallery widths="250px">
File:V13 negative cycle initialization.jpg|negative cycle initialization
File:V13 succ shortest paths no neg clcly general.jpg|succ shortest paths no neg clcly general
File:V13 succ shortest paths no neg cylce simple.jpg|succ shortest paths no neg cylce simple
File:V13 successive shortest paths iteration.jpg|successive shortest paths iteration
</gallery>
=Lecture recording 14=
{{#ev:youtube|https://www.youtube.com/watch?v=Qk4iHtTNz-E|500|right|
|frame}}

=Lecture recording 15=
<gallery widths="250px">
File:V15 Hungarian Algorithm 1.jpg|Hungarian Algorithm 1
File:V15 Hungarian Algorithm 2.jpg|Hungarian Algorithm 2
</gallery>

Lecture: Efficient Graph Algorithms

2016-02-13T09:06:44Z

Luedecke: /* Lecture recording 8 */

File:V8 augmenting path.jpg

2016-02-13T09:05:16Z

Luedecke:

File:V8 augmenting at a node.jpg

2016-02-13T09:05:03Z

Luedecke:

Lecture: Efficient Graph Algorithms

2016-02-13T09:02:49Z

Luedecke: /* Lecture recording 14 */

=Lecture recording 1=
{{#ev:youtube|https://www.youtube.com/watch?v=nw5hkRdrdb8|500|right|
|frame}}
<gallery widths=250px>
File:V1 dial 01.jpg|dial 01
</gallery>
=Lecture recording 2=
{{#ev:youtube|https://www.youtube.com/watch?v=Evt8f8kQPiY|500|right|
|frame}}
<gallery widths="250px">
File:V2 Dijkstra bidirectional Idee.jpg|Dijkstra bidirectional Idee
File:V2 Dijkstra bidirectional Korrektheit.jpg|Dijkstra bidirectional Korrektheit
File:V2 Dijkstra goaloriented Details.jpg|Dijkstra goaloriented Details
File:V2 Dijkstra goaloriented Idee.jpg|Dijkstra goaloriented Idee
File:V2 Dijkstra goaloriented Korrektheit.jpg|Dijkstra goaloriented Korrektheit
</gallery>
=Lecture recording 3=
{{#ev:youtube|https://www.youtube.com/watch?v=Lbnwwl93mHs|500|right|
|frame}}
<gallery widths="250px">
File:V3 BFS Queue.jpg|BFS Queue
File:V3 DFS lax-kleinst.jpg|DFS lax-kleinst
File:V3 DFS lexikographische Knotenreihung.jpg|DFS lexikographische Knotenreihung
File:V3 DFS nichtlexikographische Ausgabereihung.jpg|nichtlexikographische Ausgabereihung
File:V3 DFS Rueckwaertsgehen.jpg|DFS Rueckwaertsgehen
File:V3 Murmelbeweis.jpg|Murmelbeweis
</gallery>
=Lecture recording 4=
{{#ev:youtube|https://www.youtube.com/watch?v=nlIh-hR4T9M|500|right|
|frame}}
<gallery widths="250px">
File:V4 starke Zusammenhangskomponenten.jpg|starke Zusammenhangskomponenten
</gallery>
=Lecture recording 5=
{{#ev:youtube|https://www.youtube.com/watch?v=SJWdFA-b53E|500|right|
|frame}}
<gallery widths="250px">
File:V5 Artikulationspunkt.jpg|Artikulationspunkt
File:V5 Bruecke.jpg|Bruecke
File:V5 DFS 2-fache Zshkomp 1.jpg|DFS 2-fache Zshkomp 1
File:V5 DFS 2-fache Zshkomp 2.jpg|DFS 2-fache Zshkomp 2
File:V5 DFS 2-fache Zshkomp 3.jpg|DFS 2-fache Zshkomp 3
File:V5 DFS 2-fache Zshkomp 4.jpg|DFS 2-fache Zshkomp 4
File:V5 DFS 2-fache Zshkomp 5.jpg|DFS 2-fache Zshkomp 5
File:V5 Euler-Algo schematisch.jpg|Euler-Algo schematisch
File:V5 Haus vom Nikolaus 1.jpg|Haus vom Nikolaus 1
File:V5 Haus vom Nikolaus 2.jpg|Haus vom Nikolaus 2
File:V5 Haus vom Nikolaus 3.jpg|Haus vom Nikolaus 3
</gallery>
=Lecture recording 6=
{{#ev:youtube|https://www.youtube.com/watch?v=7VHBczAZ1tU|500|right|
|frame}}
<gallery widths="250px">
File:V6 Branching Terminologie.jpg|Branching Terminologie
File:V6 Branching Zykelschrumpfung.jpg|Branching Zykelschrumpfung
File:V6 Euler-Algo Beweis.jpg|Euler-Algo Beweis
File:V6 max-flow multi-source multi-target.jpg|max-flow multi-source multi-target
</gallery>
=Lecture recording 7=
{{#ev:youtube|https://www.youtube.com/watch?v=TtAXbP49VJI|500|right|
|frame}}
<gallery widths="250px">
File:V7 Branching Beweis 1.jpg|Branching Beweis 1
File:V7 Branching Beweis 2.jpg|Branching Beweis 2
File:V7 Branching falsches Beispiel.jpg|Branching falsches Beispiel
File:V7_branching_Beitrag_Hoehn.pdf|Branching Beitrag Hoehn
</gallery>
=Lecture recording 8=
{{#ev:youtube|https://www.youtube.com/watch?v=BZIZTig1fKc|500|right|
|frame}}
<gallery widths="250px">
File:V8 anti-symmetric.jpg|anti-symmetric
File:V8 Cut 1.jpg|Cut 1
File:V8 Cut 2.jpg|Cut 2
File:V8 Cut 3.jpg|Cut 3
File:V8 neuer augmentierender Pfad Bsp.jpg|neuer augmentierender Pfad Bsp
File:V8 neuer augmentierender Pfad einfach.jpg|neuer augmentierender Pfad einfach
</gallery>
=Lecture recording 9=
{{#ev:youtube|https://www.youtube.com/watch?v=eUGnz-yfPco|500|right|
|frame}}
<gallery widths="250px">
File:V9 Ahuha-Orlin Beweis.jpg|Ahuha-Orlin Beweis
File:V9 Complexity Edmonds-Karp.jpg|Complexity Edmonds-Karp
File:V9 neuer augmentierender Pfad komplex.jpg|neuer augmentierender Pfad komplex
File:V9 residual network 1.jpg|residual network 1
File:V9 residual network 2.jpg|residual network 2
</gallery>
=Lecture recording 10=
{{#ev:youtube|https://www.youtube.com/watch?v=SaPIhRYg5Q4|500|right|
|frame}}
<gallery widths="250px">
File:V10 three indians.jpg|three indians
File:V10 valid distance labeling.jpg|valid distance labeling
</gallery>
=Lecture recording 11=
{{#ev:youtube|https://www.youtube.com/watch?v=o9RcytmMCZs|500|right|
|frame}}
<gallery widths="250px">
File:V11 saturierter Schnitt.jpg|saturierter Schnitt
</gallery>
=Lecture recording 12=
{{#ev:youtube|https://www.youtube.com/watch?v=aqen34eNfs8|500|right|
|frame}}
<gallery widths="250px">
File:V12 negative Kostenfaktoren Beispiel.jpg|negative Kostenfaktoren Beispiel
File:V12 negative Kostenfaktoren konzeptionell.jpg|negative Kostenfaktoren konzeptionell
File:V12 negative Zykel Rechnung.jpg|negative Zykel Rechnung
File:V12 negativer Zykel Skizze.jpg|negativer Zykel Skizze
</gallery>

=Lecture recording 13=
{{#ev:youtube|https://www.youtube.com/watch?v=HAQwxvxVbPw|500|right|
|frame}}
<gallery widths="250px">
File:V13 negative cycle initialization.jpg|negative cycle initialization
File:V13 succ shortest paths no neg clcly general.jpg|succ shortest paths no neg clcly general
File:V13 succ shortest paths no neg cylce simple.jpg|succ shortest paths no neg cylce simple
File:V13 successive shortest paths iteration.jpg|successive shortest paths iteration
</gallery>
=Lecture recording 14=
{{#ev:youtube|https://www.youtube.com/watch?v=Qk4iHtTNz-E|500|right|
|frame}}

=Lecture recording 15=

File:V15 Hungarian Algorithm 2.jpg

2016-02-13T09:01:51Z

Luedecke:

File:V15 Hungarian Algorithm 1.jpg

2016-02-13T09:01:33Z

Luedecke:

File:V13 successive shortest paths iteration.jpg

2016-02-13T09:00:20Z

Luedecke: Luedecke uploaded a new version of "File:V13 successive shortest paths iteration.jpg"

File:V13 succ shortest paths no neg cylce simple.jpg

2016-02-13T09:00:04Z

Luedecke: Luedecke uploaded a new version of "File:V13 succ shortest paths no neg cylce simple.jpg"

File:V13 succ shortest paths no neg clcly general.jpg

2016-02-13T08:59:48Z

Luedecke: Luedecke uploaded a new version of "File:V13 succ shortest paths no neg clcly general.jpg"

File:V13 negative cycle initialization.jpg

2016-02-13T08:59:38Z

Luedecke: Luedecke uploaded a new version of "File:V13 negative cycle initialization.jpg"

File:V12 negativer Zykel Skizze.jpg

2016-02-13T08:59:24Z

Luedecke: Luedecke uploaded a new version of "File:V12 negativer Zykel Skizze.jpg"

File:V12 negative Zykel Rechnung.jpg

2016-02-13T08:59:11Z

Luedecke: Luedecke uploaded a new version of "File:V12 negative Zykel Rechnung.jpg"

File:V12 negative Kostenfaktoren konzeptionell.jpg

2016-02-13T08:58:59Z

Luedecke: Luedecke uploaded a new version of "File:V12 negative Kostenfaktoren konzeptionell.jpg"

File:V12 negative Kostenfaktoren Beispiel.jpg

2016-02-13T08:58:19Z

Luedecke: Luedecke uploaded a new version of "File:V12 negative Kostenfaktoren Beispiel.jpg"

File:V11 saturierter Schnitt.jpg

2016-02-13T08:58:06Z

Luedecke: Luedecke uploaded a new version of "File:V11 saturierter Schnitt.jpg"

File:V10 valid distance labeling.jpg

2016-02-13T08:57:48Z

Luedecke: Luedecke uploaded a new version of "File:V10 valid distance labeling.jpg"

File:V10 three indians.jpg

2016-02-13T08:57:24Z

Luedecke: Luedecke uploaded a new version of "File:V10 three indians.jpg"

File:V9 residual network 2.jpg

2016-02-13T08:57:08Z

Luedecke: Luedecke uploaded a new version of "File:V9 residual network 2.jpg"

File:V9 residual network 1.jpg

2016-02-13T08:56:54Z

Luedecke: Luedecke uploaded a new version of "File:V9 residual network 1.jpg"

File:V9 neuer augmentierender Pfad komplex.jpg

2016-02-13T08:56:38Z

Luedecke: Luedecke uploaded a new version of "File:V9 neuer augmentierender Pfad komplex.jpg"

File:V9 Complexity Edmonds-Karp.jpg

2016-02-13T08:56:31Z

Luedecke: Luedecke uploaded a new version of "File:V9 Complexity Edmonds-Karp.jpg"

File:V9 Ahuha-Orlin Beweis.jpg

2016-02-13T08:56:18Z

Luedecke: Luedecke uploaded a new version of "File:V9 Ahuha-Orlin Beweis.jpg"

File:V8 neuer augmentierender Pfad einfach.jpg

2016-02-13T08:56:05Z

Luedecke: Luedecke uploaded a new version of "File:V8 neuer augmentierender Pfad einfach.jpg"

File:V8 neuer augmentierender Pfad Bsp.jpg

2016-02-13T08:55:25Z

Luedecke: Luedecke uploaded a new version of "File:V8 neuer augmentierender Pfad Bsp.jpg"

File:V8 Cut 3.jpg

2016-02-13T08:55:08Z

Luedecke: Luedecke uploaded a new version of "File:V8 Cut 3.jpg"

File:V8 Cut 2.jpg

2016-02-13T08:54:57Z

Luedecke: Luedecke uploaded a new version of "File:V8 Cut 2.jpg"

File:V8 Cut 1.jpg

2016-02-13T08:54:22Z

Luedecke: Luedecke uploaded a new version of "File:V8 Cut 1.jpg"

File:V8 anti-symmetric.jpg

2016-02-13T08:54:05Z

Luedecke: Luedecke uploaded a new version of "File:V8 anti-symmetric.jpg"

File:V7 Branching falsches Beispiel.jpg

2016-02-13T08:53:56Z

Luedecke: Luedecke uploaded a new version of "File:V7 Branching falsches Beispiel.jpg"

File:V7 Branching Beweis 2.jpg

2016-02-13T08:53:43Z

Luedecke: Luedecke uploaded a new version of "File:V7 Branching Beweis 2.jpg"

File:V7 Branching Beweis 1.jpg

2016-02-13T08:53:35Z

Luedecke: Luedecke uploaded a new version of "File:V7 Branching Beweis 1.jpg"

File:V6 max-flow multi-source multi-target.jpg

2016-02-13T08:53:26Z

Luedecke: Luedecke uploaded a new version of "File:V6 max-flow multi-source multi-target.jpg"

File:V6 Euler-Algo Beweis.jpg

2016-02-13T08:53:05Z

Luedecke: Luedecke uploaded a new version of "File:V6 Euler-Algo Beweis.jpg"

File:V6 Branching Zykelschrumpfung.jpg

2016-02-13T08:52:55Z

Luedecke: Luedecke uploaded a new version of "File:V6 Branching Zykelschrumpfung.jpg"

File:V6 Branching Terminologie.jpg

2016-02-13T08:52:36Z

Luedecke: Luedecke uploaded a new version of "File:V6 Branching Terminologie.jpg"

File:V5 Haus vom Nikolaus 3.jpg

2016-02-13T08:52:29Z

Luedecke: Luedecke uploaded a new version of "File:V5 Haus vom Nikolaus 3.jpg"

File:V5 Haus vom Nikolaus 2.jpg

2016-02-13T08:52:18Z

Luedecke: Luedecke uploaded a new version of "File:V5 Haus vom Nikolaus 2.jpg"

File:V5 Haus vom Nikolaus 1.jpg

2016-02-13T08:52:11Z

Luedecke: Luedecke uploaded a new version of "File:V5 Haus vom Nikolaus 1.jpg"

File:V5 Euler-Algo schematisch.jpg

2016-02-13T08:52:01Z

Luedecke: Luedecke uploaded a new version of "File:V5 Euler-Algo schematisch.jpg"

File:V5 DFS 2-fache Zshkomp 5.jpg

2016-02-13T08:51:40Z

Luedecke: Luedecke uploaded a new version of "File:V5 DFS 2-fache Zshkomp 5.jpg"

File:V5 DFS 2-fache Zshkomp 4.jpg

2016-02-13T08:51:22Z

Luedecke: Luedecke uploaded a new version of "File:V5 DFS 2-fache Zshkomp 4.jpg"

File:V5 DFS 2-fache Zshkomp 3.jpg

2016-02-13T08:51:01Z

Luedecke: Luedecke uploaded a new version of "File:V5 DFS 2-fache Zshkomp 3.jpg"

File:V5 DFS 2-fache Zshkomp 2.jpg

2016-02-13T08:50:43Z

Luedecke: Luedecke uploaded a new version of "File:V5 DFS 2-fache Zshkomp 2.jpg"

File:V5 DFS 2-fache Zshkomp 1.jpg

2016-02-13T08:50:29Z

Luedecke: Luedecke uploaded a new version of "File:V5 DFS 2-fache Zshkomp 1.jpg"