Algowiki - User contributions [en]

Array list: insert at position

2014-10-14T19:03:33Z

Dkratschmann: Created page with "'''Algorithmic problem:''' Linear sequence: insert at position '''Prerequisites:''' Parameters: A key <math>\Kappa \in K, a position l \in \{0, \ldots, number()\}</math>...."

'''Algorithmic problem:''' [[Linear sequence: insert at position]]

'''Prerequisites:''' Parameters: A key <math>\Kappa \in K, a position l \in \{0, \ldots, number()\}</math>.

'''Type of algorithm:''' loop

'''Auxiliary data:'''
# A natural number sum <math>\in \mathbb{N}_0</math>, which contains the total number of all elements seen so far in the visited arrays.
# Two pointers, <math>p</math> and <math>p'</math>, of type "pointer tolist item of type array of component type <math>\Kappa</math>".

==Abstract view ==

'''Invariant:'''After <math>i \ge 0</math> iterations:
# The pointer <math>p</math> points to the array at position <math>i+1</math> in the array list.
# It is <math>sum = n_1 + \ldots + n_i</math>, where <math>n_j</math> is the value of the component n of the array list item at position <math>j \in \{1, \ldots,i\}</math>.

'''Varian:''' The pointer <math>p</math> is moved one step forward to the next array.

'''Break condition:''' It is sum <math>+ p.n \ge l</math>.

==Induction basis==

'''Abstract view:''' Set <math>p:=</math>first and <math>sum:=0</math>.

'''Implementation:''' Obvious.

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

==Induction step==

'''Abstract view:''' If the position <math>l</math> is in the current array, insert <math>\Kappa</math> (if the array is full, split it first).

'''Implementation:'''
# If sum<math>+ p.n < l</math>:
## Set sum<math>:=</math>sum<math>+ p.n</math>.
## Set <math>p:=p.next</math>.
#Otherwise:
##If <math>p.n=N</math>:
###Create a new array list item and let <math>p'</math> point to this new list item.
###Set <math>p'.next=p.next</math>.
###Set <math>p.next:=p'</math>.
###For <math>j \in \{1, \ldots, \lfloor p.n/2 \rfloor \}</math>, set <math>p'.A[\lceil p.n/2 \rceil + j]</math> and <math>p.A[\lceil p.n/2 \rceil + j]:=</math>void.
###Set <math>p'.n:=\lfloor p.n/2 \rfloor</math> and, afterwards, <math>p.n:=p.n - \lfloor p.n/2 \rfloor</math>.
## If <math>l - sum > p.n</math>:
### Set <math>m:=l - sum - p.n + 1</math>.
### Set <math>p:=p'</math>.
## Otherwise, set <math>m:=l - sum + 1</math>.
## For <math>j=p.n, \ldots, m</math> (in this order), set <math>p.A[j+1]:=p.A[j]</math>.

'''Correctness:''' Note that, in an implementation of [[Linear sequence: insert at position]], we may assume <math>l \leq</math>number(). Therefore, we do not have to care about the end of the list. In the case sum<math>+ p.n < l</math>, we simply have to update sum and <math>p</math>, which is obviously done correctly. So consider the case sum<math>+ p.n \ge l</math>, which means that the position where <math>\Kappa</math> has to be inserted is in the array list item to which <math>p</math> currently points. If that array is full, new space must be allocated. Step 2.1 does that and distributes the elements roughly equally over both items. Steps 2.2 - 2.3 ensure that <math>p</math> points to the array where to insert <math>\Kappa</math> and <math>m</math> identifies the correct insert position. Step 2.4 empties the array component where to insert the new element by moving, exactly one position forward, the value at the position and the values at all later position (which is possible because the array is not full in any case).

==Complexity==

'''Statement:''' Linear in the length of the sequence in the worst case.

'''Proof:''' Obvious.

==Further information==

Array list: find

2014-10-14T18:36:29Z

Dkratschmann: Created page with "'''Algorithmic problem:''' Linear sequence: find '''Prerequisites:''' None. '''Type of algorithm:''' loop '''Auxiliary data:''' A pointer <math>p</math> of type "pointe..."

'''Algorithmic problem:''' [[Linear sequence: find]]

'''Prerequisites:''' None.

'''Type of algorithm:''' loop

'''Auxiliary data:''' A pointer <math>p</math> of type "pointer to list item of array lists of compnent type <math>\Kappa</math>".

== Abstract view ==

'''Invariant:''' After <math>i \ge 0</math> iterations:
# The pointer <math>p</math> points to the list item at position <math>i + 1</math> (or is void if no such item exists).
# The first <math>i</math> arrays in the list do not contain <math>\Kappa</math>.

'''Variant:''' The pointer <math>p</math> is moved one step forward to the next array list item.

'''Break condition:''' Either <math>p=</math>void or, otherwise, <math>\Kappa \in \{p.A[1], \ldots, p.A[p.n]\}</math>.

== Induction basis ==

'''Abstract view:''' Set <math>p:=</math> first.

'''Implementation:''' Obvious.

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

== Induction step ==

'''Abstract view:'''
# Terminate the algorithm if the end of the list is reached or, otherwise, if <math>\Kappa</math> is found in the current array.
# Otherwise, <math>p</math> is moved one step forward to the next array.

'''Implementation:'''
# If <math>p=</math>void, terminate the algorithm and return <math>false</math>.
# Otherwise, if <math>p.A[j] = \Kappa</math> for some <math>j \in \{1, \ldots, p.n\}</math>, set <math>p:=p.next</math>.

'''Correctness:''' Obvious.

== Complexity ==

'''Statement:''' Linear in the length of the sequence in the worst case.

'''Proff:''' Obvious.

Maximum spanning forest

2014-10-06T20:01:22Z

Dkratschmann:

== Input ==
# An [[undirected graph]] <math>G = (V,E)</math>, not necessarily connected.
# An edge length <math>l(e) \in \mathbb{R}_0^+</math> for each edge <math>e \in E</math>.

== Output ==
An [[undirected forest]] <math> F= (V,E_F)</math> such that <math>E_F \subseteq E</math>.

== Objective ==

'''Maximize:''' <math>\sum{}{}_{e \in E_F}l(e)</math>.

== Complexity ==

Polynomial.

== Known algorithms ==

[[Kruskal]]

== Known variants ==

== Remark ==

Maximum spanning forest

2014-10-06T20:01:03Z

Dkratschmann: Created page with "== Input == # An undirected graph <math>G = (V,E)</math>, not necessarily connected. # An edge length <math>l(e) \in \mathbb{R}_0^+</math> for each edge <math>e \in E</mat..."

== Input ==
# An [[undirected graph]] <math>G = (V,E)</math>, not necessarily connected.
# An edge length <math>l(e) \in \mathbb{R}_0^+</math> for each edge <math>e \in E</math>.

== Output ==
An [[undirected forest]] <math> F= (V,E_F)</math> such that <math>E_F \subseteq E</math>.

== Objective ==

'''Maximize:''' <math>\sum{}{}_{e \in E_F}l(e)</math>.

== Complexity ==

Polynomial

== Known algorithms ==

[[Kruskal]]

== Known variants ==

== Remark ==

Shortest paths by repeated squaring

2014-10-06T19:50:53Z

Dkratschmann: Created page with "'''Algorithmic problem:''' All pairs shortest paths '''Prerequisites:''' None '''Type of algorithm:''' loop # A distance-valued <math>(n \times n)</math>-matrix <mat..."

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

'''Prerequisites:''' None

'''Type of algorithm:''' loop
# A [[distance-valued]] <math>(n \times n)</math>-matrix <math>M</math>, where <math>n = |V|</math>. The eventual contents of <math>M</math> will be returned as the result of the algorithm.
# A <math>(n \times n)</math>-matrix <math>M</math> such that <math>M_0(v,w)</math>, if <math>(v,w) \in A</math>, and <math>M_0(v,w)=+\infty</math>, otherwise.

'''Auxilliary data:'''

== Abstract view ==

'''Invariant:''' After <math>i \ge 0</math> iterations, it is <math>M=M_0^{2i}</math>, where powers of a matrix are defined as [[Path]].

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

'''Break condition:''' It is <math>\lceil log_2 |V| \rceil</math>.

== Induction basis ==

'''Abstract view:''' Initiallized <math>M</math> by setting
* <math>M(v,w) = 0</math> for all <math>v \in V</math>,
* <math>M(v,w) = l(v,w)</math> for <math>(v,w) \in A</math> and
* <math>M(v,w) = +\infty</math> otherwise.

'''Implementation:''' Obvious.

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

== Induction step ==

'''Abstract view:''' For all <math>v, w \in V</math>, set <math>M(v,w) := min \{ M(v,w), min \{ M(v,u) + M(u,w) | u \in V \setminus_{ \{v,w\} } \} \}</math>.

'''Implementation:''' Obvious.

'''Correctness:''' Maintenance of the invariant is obvious. The claim now follows from the explanations of powers of the distance matrix as [[Path]] and from the fact that a shortest path cannot have more than <math>|V| </math> nodes.

== Complexity ==

'''Statement:''' The asymptotic complexity is <math>\Theta(n^3 log(n))</math> in the best and worst case.

'''Proof:''' The main loop terminates after <math>\lceil log_2 n \rceil</math> iterations. In each iteration of this loop, we update all <math>n^2</math> matrix entries, and computing one update value requires <math>\Theta(n)</math> steps.

Floyd-Warshall

2014-10-04T14:46:18Z

Dkratschmann:

<div class="plainlinks" style="float:right;margin:0 0 5px 5px; border:1px solid #AAAAAA; width:auto; padding:1em; margin: 0px 0px 1em 1em;">
<div style="font-size: 1.8em;font-weight:bold;text-align: center;margin:0.2em 0 1em 0">Floyd-Warshall</div>

<div style="font-size: 1.2em; margin:.5em 0 1em 0; text-align:center">whatever</div>

<div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://google.de Openlearnware]</div>
</div>

'''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 [[distance-valued]] <math>(n \times n)</math> matrix <math>M</math>
# C An ordering of all nodes, that is, <math>V = \{u_1, \ldots ,u_n\}</math>

== Abstract View ==
'''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>.

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

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

== Induction basis ==
'''Abstract view:''' <math>\forall 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:'''

'''Implementation:'''

'''Correctness:''' Let <math>p</math> denote a shoortest <math>(v,w</math>-path subject to the constraint that all [[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 [[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.

Floyd-Warshall

2014-10-04T14:37:46Z

Dkratschmann:

<div class="plainlinks" style="float:right;margin:0 0 5px 5px; border:1px solid #AAAAAA; width:auto; padding:1em; margin: 0px 0px 1em 1em;">
<div style="font-size: 1.8em;font-weight:bold;text-align: center;margin:0.2em 0 1em 0">Floyd-Warshall</div>

<div style="font-size: 1.2em; margin:.5em 0 1em 0; text-align:center">whatever</div>

<div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/dijkstra-2310 Openlearnware]</div>
</div>

'''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 [[distance-valued]] <math>(n \times n)</math> matrix <math>M</math>
# C An ordering of all nodes, that is, <math>V = \{u_1, \ldots ,u_n\}</math>

== Abstract View ==
'''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>.

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

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

== Induction basis ==
'''Abstract view:''' <math>\forall 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:'''

'''Implementation:'''

'''Correctness:''' Let <math>p</math> denote a shoortest <math>(v,w</math>-path subject to the constraint that all [[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 [[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.

Floyd-Warshall

2014-10-04T14:37:23Z

Dkratschmann:

<div class="plainlinks" style="float:right;margin:0 0 5px 5px; border:1px solid #AAAAAA; width:auto; padding:1em; margin: 0px 0px 1em 1em;">
<div style="font-size: 1.8em;font-weight:bold;text-align: center;margin:0.2em 0 1em 0">Dijkstra</div>

<div style="font-size: 1.2em; margin:.5em 0 1em 0; text-align:center">whatever</div>

<div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/dijkstra-2310 Openlearnware]</div>
</div>

'''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 [[distance-valued]] <math>(n \times n)</math> matrix <math>M</math>
# C An ordering of all nodes, that is, <math>V = \{u_1, \ldots ,u_n\}</math>

== Abstract View ==
'''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>.

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

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

== Induction basis ==
'''Abstract view:''' <math>\forall 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:'''

'''Implementation:'''

'''Correctness:''' Let <math>p</math> denote a shoortest <math>(v,w</math>-path subject to the constraint that all [[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 [[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.

Floyd-Warshall

2014-10-04T14:36:43Z

Dkratschmann:

'''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 [[distance-valued]] <math>(n \times n)</math> matrix <math>M</math>
# C An ordering of all nodes, that is, <math>V = \{u_1, \ldots ,u_n\}</math>
<div class="plainlinks" style="float:right;margin:0 0 5px 5px; border:1px solid #AAAAAA; width:auto; padding:1em; margin: 0px 0px 1em 1em;">
<div style="font-size: 1.8em;font-weight:bold;text-align: center;margin:0.2em 0 1em 0">Dijkstra</div>

<div style="font-size: 1.2em; margin:.5em 0 1em 0; text-align:center">whatever</div>

<div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/dijkstra-2310 Openlearnware]</div>
</div>

== Abstract View ==
'''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>.

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

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

== Induction basis ==
'''Abstract view:''' <math>\forall 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:'''

'''Implementation:'''

'''Correctness:''' Let <math>p</math> denote a shoortest <math>(v,w</math>-path subject to the constraint that all [[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 [[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.

Floyd-Warshall

2014-10-04T14:33:13Z

Dkratschmann: Created page with "'''Algorithmic problem:''' All pairs shortest paths '''Prerequisites:''' None '''Type of algorithm:''' loop '''Auxilliary data:''' # A constant representing the number..."

'''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 [[distance-valued]] <math>(n \times n)</math> matrix <math>M</math>
# C An ordering of all nodes, that is, <math>V = \{u_1, \ldots ,u_n\}</math>

== Abstract View ==
'''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>.

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

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

== Induction basis ==
'''Abstract view:''' <math>\forall 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:'''

'''Implementation:'''

'''Correctness:''' Let <math>p</math> denote a shoortest <math>(v,w</math>-path subject to the constraint that all [[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 [[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.

All pairs shortest paths

2014-10-04T14:02:18Z

Dkratschmann:

== Input ==

# A [[directed Graph]] <math>G = (V,A)</math>
# An arc length <math>l(a) \in \mathbb{R}</math> for each arc <math>a \in A</math>

== Ouptut ==

For each pair <math>(v,w) \in A</math> with <math> v,w \in V</math>, the length <math>\Delta(v,w)</math> of a shortest <math>(v,w)</math>-path in <math>G</math> with respect to <math>l</math>.

== Complexity ==
Polynomial

== Known algorithms ==
# [[Floyd-Warshall]]
# [[Bellman-Ford]]
# [[Shortest oaths by repeated squaring]] (varian of Bellman-Ford)

All pairs shortest paths

2014-10-04T13:59:27Z

Dkratschmann:

== Input ==

# A directed Graph <math>G = (V,A)</math>
# An arc length <math>l(a) \in \mathbb{R}</math> for each arc <math>a \in A</math>

== Ouptut ==

For each pair <math>(v,w) \in A</math> with <math> v,w \in V</math>, the length <math>\Delta(v,w)</math> of a shortest <math>(v,w)</math>-path in <math>G</math> with respect to <math>l</math>.

== Complexity ==
Polynomial

== Known algorithms ==
# [[Floyd-Warshall]]
# [[Bellman-Ford]]
# [[Shortest oaths by repeated squaring]] (varian of Bellman-Ford)

All pairs shortest paths

2014-10-04T13:48:46Z

Dkratschmann: Created page with "== Input == * A directed Graph <math>G = (V,A)</math> * An arc length <math>l(a) \in \mathbb{R}</math> for each arc <math>a \in A</math> == Ouptut == For each pair <math>(v..."

== Input ==

* A directed Graph <math>G = (V,A)</math>
* An arc length <math>l(a) \in \mathbb{R}</math> for each arc <math>a \in A</math>

== Ouptut ==

For each pair <math>(v,w) \in A</math> with <math> v,w \in V</math>, the length <math>\Delta(v,w)</math> of a shortest <math>(v,w)</math>-path in <math>G</math> with respect to <math>l</math>.

== Complexity ==
Polynomial

== Known algorithms ==
* [[Floyd-Warshall]]
* [[Bellman-Ford]]
* [[Shortest oaths by repeated squaring]] (varian of Bellman-Ford)

Main Page

2014-09-30T21:00:38Z

Dkratschmann: /* Graph Theory */

== News ==
* <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]

== To Do ==
=== Notations ===
* [[Asymptotic notation]]
* [[L' Hospital]]
* [[Master theorem]]
=== Problems ===
* [[Maximum matching problem]]
* [[Max-Flow Problems]]
* [[Min-Cost Flow Problems]]
* [[Shortest Paths Problems]]
** [[All pairs shortest paths]]
*** [[Floyd-Warshall]]
*** [[Bellman-Ford]]
*** [[Shortest paths by repeated squaring]] (variant of Bellman-Ford)
** [[Single source shortest paths]]
*** [[Dijkstra]]
** [[Single source single target shortest paths]]
*** [[A*]]
* [[Maximum spanning forest]]
* [[Problems on Sequences]]
** [[Basic Problems on Sequences]]
*** [[Find an element in a sequence]]
*** [[Insert an element in a sequence]]
*** [[Median]]
*** [[Merging two sorted sequences]]
** [[Pattern Matching]]
*** [[One-dimensional string matching]]
*** [[String matching]]
** [[Sorting]]
*** [[Sorting based on pairwise comparison]]
*** [[Sorting Sequences of Strings]]

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

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

=== Sorting Algorithms ===
* [[Bubble]]
* [[Insertion Sort]]
* [[Quick Sort]]
* [[Bubble Sort]]
* [[Merge Sort]]
* [[Bucket Sort]]
* [[Selection Sort]]
* [[Bogo Sort]]

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

=== 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:Rotate]]
* [[B-Tree:Merge]]
* [[B-Tree:Split-Child]]
* [[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]]
* [[k-partite Graph]]
* [[Negative Paths]]

=== Graph Algorithms ===
* [[Dijkstra]]
* [[Kruskal]]
* [[Prim]]
* [[Bellman-Ford]]
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]

=== Flow Algorithms ===
* [[Ford-Fulkerson]]
=== Data Structures ===
* [[Linked List]]
* [[Array List]]
* [[First In - First Out]]
* [[First In - Ieast Out]]
* [[Double Linked List]]
* [[Heaps]] (DONE (Heap as Array))
* [[Min-Max Heaps]]
* [[Hash Table]]
* [[Directed Tree]]
* [[Binary Search Tree]]
* [[B-Trees]]
* [[Decision Tree]]
* [[Red-Black Tree]]
* [[Graphs]]

=== Other Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic Redundancy Check]]
* [[Eulcid]]
* [[Gauss]]
* [[Discrete Fourier transform]]
* [[Fast Fourier transform]]
* [[Bresenham]]
* [[Round Robin]]
* [[Seperate and Conquer]]
* [[Message-Digest Algorithm]]
* [[Secure Hash Algorithm]]
* [[Sequent calculus]]
* [[Resolution calculus]]
* [[Cocke-Younger-Kasami Algorithm]]
* [[Distance Vector Routing]]
* [[Link State Round]]
* [[Z Buffer Algorithm]]
* [[Marching Squares]]
* [[Marching Cubes]]
* [[Bottom-Up Heapsort]]
* [[Radixsort]]
* [[Median Cut]]
* [[Pancake sorting]]
* [[Karnaugh-Veitch Diagramm]]
* [[Delanuay Triangulation]]
* [[Backtracking]]
* [[Alpha–beta pruning]]
* [[Beam search]]
* [[Best-first search]]
* [[Bidirectional search]]
* [[Borůvka's algorithm]]
* [[Branch and bound]]
* [[D*]]
* [[Depth-limited search]]
* [[Edmonds' algorithm]]
* [[Fringe search]]
* [[Hill climbing]]
* [[IDA*]]
* [[Iterative deepening depth-first search]]
* [[Jump point search]]
* [[Lexicographic breadth-first search]]
* [[SMA*]]
* [[Uniform-cost search]]

=== Other Data Structures (LOCKED) ===
* [[Adelson-Velskii and Landis' tree]]
* [[Patricia-Trie]]
* [[Suffix Tree]]
* [[Huffmann Tree]]
* [[Binary Expression Tree]]
* [[Hash Set]]
* [[Incidence Matrix]]
* [[Voronoi Diagramm]]
* [[Quad Tree]]
* [[Oct Tree]]
* [[kd Tree]]
* [[Binary space partitioning]]