Algowiki - User contributions [en]

Max-Flow Problems

2014-12-02T13:26:16Z

Mahn89: /* Generalizations */

== Basic definitions ==

# [[Basic graph definitions]]
# [[Basic flow definitions]]

== Standard version ==

'''Input:'''
# A directed graph <math>G=(V,A)</math>.
# A '''source node''' <math>s\in V</math> and a '''target (a.k.a. sink) node''' <math>t\in V</math>.
# A nonnegative '''upper bound (a.k.a. capacity)''' <math>u(a)</math> for each arc <math>a\in A</math>.

'''Output:'''
A [[Basic flow definitions#Feasible flow|feasible <math>(s,t)</math>-flow]] that has maximum [[Basic flow definitions#Flow value|flow value]] among all feasible <math>(s,t)</math>-flows.

== Known algorithms ==

# [[Ford-Fulkerson]]
# [[Edmonds-Karp]]
# [[Ahuja-Orlin]]
# [[Dinic]]
# [[Preflow-push]]
# [[FIFO preflow-push]]
# [[Preflow-push with excess scaling]]

== Generalizations ==

# For each arc <math>a\in A</math>, there is a '''lower bound''' <math>\ell(a)</math>, and <math>f(a)\geq\ell(a)</math> is additionally required. The lower bounds need not be nonnegative, so the flow values need not be nonnegative, either. This version is often called '''maximum flow with edge demands'''. It may be reduced to solving two instances of the standard version as follows:
## First, we construct a new graph <math>G'=(V',A')</math> as follows: We add a super-source <math>s'</math> and a super-target <math>t'</math> to <math>V</math>. Next, for every node <math>v\in V</math>, we add an arc <math>(s',v)</math> and an arc <math>(v,t')</math> to <math>A</math>. Finally we add an arc <math>(t,s)</math> to <math>A</math>, if not in <math>A</math> yet.
## For all arcs <math>a\in A</math>, we set <math>\ell'(a):=0</math>. For each node <math>v\in V</math>, we set
##:<math>u'(s',v):=\sum_{(w,v)\in A}\ell(w,v)</math> and <math>u'(v,t'):=\sum_{(v,w)\in A} \ell(v,w)</math>.
##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.
## It is easy to see that there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math> if, and only if, all arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are saturated. This the case if, and only if, the maximum flow <math>f'</math> in <math>G</math> from <math>s'</math> to <math>t'</math> with respect to <math>\ell'</math> and <math>u'</math> yields a flow of value <math>\sum_{a\in A}\ell(a)</math>.
## More specifically, for <math>(v,w)\in A</math>, we set <math>f(v,w):=f'(v,w)+\ell(v,w)</math>.[[File:Maxflowmultiplesource.png|350px|thumb|right|Max-Flow Problem with several sources and targets]]
# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").
# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow an the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).
# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.

Max-Flow Problems

2014-12-02T13:23:30Z

Mahn89: /* Generalizations */

== Basic definitions ==

# [[Basic graph definitions]]
# [[Basic flow definitions]]

== Standard version ==

'''Input:'''
# A directed graph <math>G=(V,A)</math>.
# A '''source node''' <math>s\in V</math> and a '''target (a.k.a. sink) node''' <math>t\in V</math>.
# A nonnegative '''upper bound (a.k.a. capacity)''' <math>u(a)</math> for each arc <math>a\in A</math>.

'''Output:'''
A [[Basic flow definitions#Feasible flow|feasible <math>(s,t)</math>-flow]] that has maximum [[Basic flow definitions#Flow value|flow value]] among all feasible <math>(s,t)</math>-flows.

== Known algorithms ==

# [[Ford-Fulkerson]]
# [[Edmonds-Karp]]
# [[Ahuja-Orlin]]
# [[Dinic]]
# [[Preflow-push]]
# [[FIFO preflow-push]]
# [[Preflow-push with excess scaling]]

== Generalizations ==

# For each arc <math>a\in A</math>, there is a '''lower bound''' <math>\ell(a)</math>, and <math>f(a)\geq\ell(a)</math> is additionally required. The lower bounds need not be nonnegative, so the flow values need not be nonnegative, either. This version is often called '''maximum flow with edge demands'''. It may be reduced to solving two instances of the standard version as follows:
## First, we construct a new graph <math>G'=(V',A')</math> as follows: We add a super-source <math>s'</math> and a super-target <math>t'</math> to <math>V</math>. Next, for every node <math>v\in V</math>, we add an arc <math>(s',v)</math> and an arc <math>(v,t')</math> to <math>A</math>. Finally we add an arc <math>(t,s)</math> to <math>A</math>, if not in <math>A</math> yet.
## For all arcs <math>a\in A</math>, we set <math>\ell'(a):=0</math>. For each node <math>v\in V</math>, we set
##:<math>u'(s,v):=\sum_{(w,v)\in A}\ell(w,v)</math> and <math>u'(v,t):=\sum_{(v,w)\in A} \ell(v,w)</math>.
##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.
## It is easy to see that there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math> if, and only if, all arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are saturated. This the case if, and only if, the maximum flow <math>f'</math> in <math>G</math> from <math>s'</math> to <math>t'</math> with respect to <math>\ell'</math> and <math>u'</math> yields a flow of value <math>\sum_{a\in A}\ell(a)</math>.
## More specifically, for <math>(v,w)\in A</math>, we set <math>f(v,w):=f'(v,w)+\ell(v,w)</math>.[[File:Maxflowmultiplesource.png|350px|thumb|right|Max-Flow Problem with several sources and targets]]
# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").
# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow an the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).
# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.

Branching by Edmonds

2014-12-02T13:02:18Z

Mahn89: /* Recursive step */

== Abstract view ==

'''Algorithmic problem:''' [[Maximum branching]]

'''Definition:'''
# An arc <math>(v,w)\in A</math> is '''critical''' for <math>w\in V</math> if its weight is not smaller than the weight of any other incoming arc of <math>w</math>.
# A '''critical subgraph''' <math>G'=(V,A')</math> of <math>G</math> contains exactly one incoming arc <math>(v,w)\in A</math> for each node <math>w\in V</math> of positive indegree, where <math>(v,w)</math> is critical.

'''Type of algorithm:''' recursion

'''Invariant:''' The output of a recursive call is a maximum branching of the weighted graph that was the input for this recursive call.

== Recursion anchor ==

'''Abstract view:''' Terminate if <math>G'</math> is cycle-free.

'''Proof:'''
If <math>G'</math> is cycle-free, it is a branching. Consider some other branching <math>B</math>. We have to show that <math>B</math> does not have more total weight than <math>G'</math>.

By definition, a critical graph contains one incoming arc for each node that does have incoming arcs. Therefore, for each arc <math>a</math> of <math>B</math>, there is an arc <math>a'</math> in <math>G'</math> pointing to the same node. Due to the choice of arcs for <math>G'</math>, it is <math>w(a)\leq w(a')</math>.

== Recursive step ==
[[File:Edmonds max branching ani 10000.gif|thumb|350px|''animated gif:'' Branching by Edmonds]]
'''Abstract view:'''
# Compute a critical subgraph <math>G'=(V,A')</math> for the input graph <math>G</math>.
# Identify some cycle <math>C</math> in <math>G'</math>.
# Let <math>W</math> denote the minimum weight of all arcs on <math>C</math>.
# For every arc <math>(v,w)\in A</math> pointing from some node <math>v</math> outside <math>C</math> to some node <math>w</math> on <math>C</math>:
##Decrease the weight of <math>(v,w)</math> by <math>w(v',w)-W\geq 0</math>, where <math>(v',w)</math> is the incoming arc of <math>w</math> on <math>C</math>.
## If the new weight of <math>(v,w)</math> is not positive, remove <math>(v,w)</math> from <math>G</math>.
# Shrink <math>C</math> into one new super-node, where every arc pointing to (resp., from) some node on <math>C</math> now points to (from) that super-node.
# Call the algorithm recursively for the modified weighted graph after shrinking, giving branching <math>B</math>.
# Unshrink the graph.
# Add all arcs of <math>C</math> to <math>B</math> giving <math>B'</math>.
# If <math>B</math> contains an arc <math>(v,w)</math> such that <math>v</math> is outside <math>C</math> and <math>w</math> is on <math>C</math>: remove the incoming arc of <math>w</math> on <math>C</math> from <math>B</math>; otherwise, remove one arc with weight <math>W</math> on <math>C</math>. Let <math>B''</math> be the result in both cases.
# Return <math>B''</math>.

'''Proof:'''
Obviously, <math>B''</math> is a branching, so we have to prove that it has maximum weight among all branchings in <math>G</math>. Let <math>B_{\mathrm{opt}}</math> be a maximum branching in <math>G</math> such that, among all maximum branchings in <math>G</math>, <math>B_{\mathrm{opt}}</math> shares as many arcs as possible with <math>B''</math>.

Let <math>C'</math> be a cycle of <math>G'</math> (the case <math>C'=C</math> not excluded). First we show that <math>B_{\mathrm{opt}}</math> contains all arcs of <math>C'</math> except one. So, suppose for a contradiction that <math>B_{\mathrm{opt}}</math> does not contain some of the arcs of <math>C'</math>, say, <math>(v_1,w_1),\ldots,(v_k,w_k)</math> with <math>k>1</math>.

Replacing the incoming arc of any <math>w_i</math> by <math>(v_i,w_i)</math> in <math>B_{\mathrm{opt}}</math> and doing nothing else, would not decrease the total weight. Since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>, such a replacement cannot result in a branching anymore. Since the indegrees do not change by that replacement, this means that adding <math>(v_i,w_i)</math> to <math>B_{\mathrm{opt}}</math> would close a cycle. In other words, there is a path <math>p_i</math> in <math>B_{\mathrm{opt}}</math> from <math>w_i</math> to <math>v_i</math>. Each path <math>p_i</math> must enter <math>C</math> at one of the nodes <math>w_j</math> because, otherwise, the node where <math>p_i</math> enters <math>C'</math> had two incoming arcs in <math>B_{\mathrm{opt}}</math>: the incoming arc on <math>C'</math> and the arc over which <math>p_i</math> enters <math>C'</math>. However, this would imply that there is a cycle in the union of all paths <math>p_i</math> plus all arcs of <math>C''</math> '''not''' in <math>\{(v_1,w_1),\ldots,(v_k,w_k)\}</math>. This union is a subset of <math>B_{\mathrm{opt}}</math>, which yields the desired contradiction.

Now we know that <math>B_{\mathrm{opt}}</math> contains all arcs except one on all cycles of <math>G'</math>. Note that, for any node not on a cycle, the incoming branching arc may be freely chosen without any effect on the rest. So, since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>,<math>B_{\mathrm{opt}}</math> and <math>B''</math> agree on all of these choices. Further note that all cycles of <math>G'</math> are node-disjoint. In summary, we may compare <math>B_{\mathrm{opt}}</math> and <math>B'</math> on each cycle of <math>G'</math> separately.

For <math>C</math>, complete agreement between <math>B_{\mathrm{opt}}</math> and <math>B''</math> follows from the observation that the choice of incoming arcs for all nodes on <math>C</math> is optimal in <math>B''</math> due to the specific modification of the arc weights. And for all other cycles of <math>G'</math>, complete agreement follows from the induction hypothesis. In both cases, we again used the specific choice of <math>B_{\mathrm{opt}}</math> to be as close to <math>B''</math> as possible.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}((n+m)\cdot n)</math> in the worst case, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
Using [[Depth-first search|DFS]] for cycle detection, each recursive step requires <math>\mathcal{O}(n+m)</math>. In each shrink operation, the number of nodes decreases, so the recursion depth is <math>\mathcal{O}(n)</math>.

'''Remark:'''
More sophisticated implementations of this algorithm yield better asymptotic complexities.

== Remarks ==

# The unshrink operation requires that the shrink operation performs some bookkeeping: For the super-node, a cyclically ordered sequence of all nodes and arcs on <math>C</math> (or an equivalent bulk of information) must be attached to a super-node.
# Several cycles may be discovered simultaneously by one run of [[Depth-first search|DFS]]. Note that all cycles in a critical graph are node-disjoint, because no node has more than one incoming arc. Therefore, several cycles may be handled in the same recursive call, without any interference.

File:Edmonds max branching ani 10000.gif

2014-12-02T12:51:22Z

Mahn89:

File:Edmonds max branching ani.gif

2014-12-02T12:49:31Z

Mahn89: Mahn89 uploaded a new version of "File:Edmonds max branching ani.gif"

Branching by Edmonds

2014-11-27T11:03:48Z

Mahn89: /* Recursive step */

== Abstract view ==

'''Algorithmic problem:''' [[Maximum branching]]

'''Definition:'''
# An arc <math>(v,w)\in A</math> is '''critical''' for <math>w\in V</math> if its weight is not smaller than the weight of any other incoming arc of <math>w</math>.
# A '''critical subgraph''' <math>G'=(V,A')</math> of <math>G</math> contains exactly one incoming arc <math>(v,w)\in A</math> for each node <math>w\in V</math> of positive indegree, where <math>(v,w)</math> is critical.

'''Type of algorithm:''' recursion

'''Invariant:''' The output of a recursive call is a maximum branching of the weighted graph that was the input for this recursive call.

== Recursion anchor ==

'''Abstract view:''' Terminate if <math>G'</math> is cycle-free.

'''Proof:'''
If <math>G'</math> is cycle-free, it is a branching. Consider some other branching <math>B</math>. We have to show that <math>B</math> does not have more total weight than <math>G'</math>.

By definition, a critical graph contains one incoming arc for each node that does have incoming arcs. Therefore, for each arc <math>a</math> of <math>B</math>, there is an arc <math>a'</math> in <math>G'</math> pointing to the same node. Due to the choice of arcs for <math>G'</math>, it is <math>w(a)\leq w(a')</math>.

== Recursive step ==
[[File:Edmonds max branching ani.gif|mini|framed||right|''animated gif:'' Branching by Edmonds]]
'''Abstract view:'''
# Compute a critical subgraph <math>G'=(V,A')</math> for the input graph <math>G</math>.
# Identify some cycle <math>C</math> in <math>G'</math>.
# Let <math>W</math> denote the minimum weight of all arcs on <math>C</math>.
# For every arc <math>(v,w)\in A</math> pointing from some node <math>v</math> outside <math>C</math> to some node <math>w</math> on <math>C</math>:
##Decrease the weight of <math>(v,w)</math> by <math>w(v',w)-W\geq 0</math>, where <math>(v',w)</math> is the incoming arc of <math>w</math> on <math>C</math>.
## If the new weight of <math>(v,w)</math> is not positive, remove <math>(v,w)</math> from <math>G</math>.
# Shrink <math>C</math> into one new super-node, where every arc pointing to (resp., from) some node on <math>C</math> now points to (from) that super-node.
# Call the algorithm recursively for the modified weighted graph after shrinking, giving branching <math>B</math>.
# Unshrink the graph.
# Add all arcs of <math>C</math> to <math>B</math> giving <math>B'</math>.
# If <math>B</math> contains an arc <math>(v,w)</math> such that <math>v</math> is outside <math>C</math> and <math>w</math> is on <math>C</math>: remove the incoming arc of <math>w</math> on <math>C</math> from <math>B</math>; otherwise, remove one arc with weight <math>W</math> on <math>C</math>. Let <math>B''</math> be the result in both cases.
# Return <math>B''</math>.

'''Proof:'''
Obviously, <math>B''</math> is a branching, so we have to prove that it has maximum weight among all branchings in <math>G</math>. Let <math>B_{\mathrm{opt}}</math> be a maximum branching in <math>G</math> such that, among all maximum branchings in <math>G</math>, <math>B_{\mathrm{opt}}</math> shares as many arcs as possible with <math>B''</math>.

Let <math>C'</math> be a cycle of <math>G'</math> (the case <math>C'=C</math> not excluded). First we show that <math>B_{\mathrm{opt}}</math> contains all arcs of <math>C'</math> except one. So, suppose for a contradiction that <math>B_{\mathrm{opt}}</math> does not contain some of the arcs of <math>C'</math>, say, <math>(v_1,w_1),\ldots,(v_k,w_k)</math> with <math>k>1</math>.

Replacing the incoming arc of any <math>w_i</math> by <math>(v_i,w_i)</math> in <math>B_{\mathrm{opt}}</math> and doing nothing else, would not decrease the total weight. Since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>, such a replacement cannot result in a branching anymore. Since the indegrees do not change by that replacement, this means that adding <math>(v_i,w_i)</math> to <math>B_{\mathrm{opt}}</math> would close a cycle. In other words, there is a path <math>p_i</math> in <math>B_{\mathrm{opt}}</math> from <math>w_i</math> to <math>v_i</math>. Each path <math>p_i</math> must enter <math>C</math> at one of the nodes <math>w_j</math> because, otherwise, the node where <math>p_i</math> enters <math>C'</math> had two incoming arcs in <math>B_{\mathrm{opt}}</math>: the incoming arc on <math>C'</math> and the arc over which <math>p_i</math> enters <math>C'</math>. However, this would imply that there is a cycle in the union of all paths <math>p_i</math> plus all arcs of <math>C''</math> '''not''' in <math>\{(v_1,w_1),\ldots,(v_k,w_k)\}</math>. This union is a subset of <math>B_{\mathrm{opt}}</math>, which yields the desired contradiction.

Now we know that <math>B_{\mathrm{opt}}</math> contains all arcs except one on all cycles of <math>G'</math>. Note that, for any node not on a cycle, the incoming branching arc may be freely chosen without any effect on the rest. So, since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>,<math>B_{\mathrm{opt}}</math> and <math>B''</math> agree on all of these choices. Further note that all cycles of <math>G'</math> are node-disjoint. In summary, we may compare <math>B_{\mathrm{opt}}</math> and <math>B'</math> on each cycle of <math>G'</math> separately.

For <math>C</math>, complete agreement between <math>B_{\mathrm{opt}}</math> and <math>B''</math> follows from the observation that the choice of incoming arcs for all nodes on <math>C</math> is optimal in <math>B''</math> due to the specific modification of the arc weights. And for all other cycles of <math>G'</math>, complete agreement follows from the induction hypothesis. In both cases, we again used the specific choice of <math>B_{\mathrm{opt}}</math> to be as close to <math>B''</math> as possible.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}((n+m)\cdot n)</math> in the worst case, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
Using [[Depth-first search|DFS]] for cycle detection, each recursive step requires <math>\mathcal{O}(n+m)</math>. In each shrink operation, the number of nodes decreases, so the recursion depth is <math>\mathcal{O}(n)</math>.

'''Remark:'''
More sophisticated implementations of this algorithm yield better asymptotic complexities.

== Remarks ==

# The unshrink operation requires that the shrink operation performs some bookkeeping: For the super-node, a cyclically ordered sequence of all nodes and arcs on <math>C</math> (or an equivalent bulk of information) must be attached to a super-node.
# Several cycles may be discovered simultaneously by one run of [[Depth-first search|DFS]]. Note that all cycles in a critical graph are node-disjoint, because no node has more than one incoming arc. Therefore, several cycles may be handled in the same recursive call, without any interference.

Branching by Edmonds

2014-11-27T11:01:02Z

Mahn89: /* Recursive step */

== Abstract view ==

'''Algorithmic problem:''' [[Maximum branching]]

'''Definition:'''
# An arc <math>(v,w)\in A</math> is '''critical''' for <math>w\in V</math> if its weight is not smaller than the weight of any other incoming arc of <math>w</math>.
# A '''critical subgraph''' <math>G'=(V,A')</math> of <math>G</math> contains exactly one incoming arc <math>(v,w)\in A</math> for each node <math>w\in V</math> of positive indegree, where <math>(v,w)</math> is critical.

'''Type of algorithm:''' recursion

'''Invariant:''' The output of a recursive call is a maximum branching of the weighted graph that was the input for this recursive call.

== Recursion anchor ==

'''Abstract view:''' Terminate if <math>G'</math> is cycle-free.

'''Proof:'''
If <math>G'</math> is cycle-free, it is a branching. Consider some other branching <math>B</math>. We have to show that <math>B</math> does not have more total weight than <math>G'</math>.

By definition, a critical graph contains one incoming arc for each node that does have incoming arcs. Therefore, for each arc <math>a</math> of <math>B</math>, there is an arc <math>a'</math> in <math>G'</math> pointing to the same node. Due to the choice of arcs for <math>G'</math>, it is <math>w(a)\leq w(a')</math>.

== Recursive step ==
[[File:Edmonds max branching ani.gif|miniatur|right|''animated gif:'' Branching by Edmonds]]
'''Abstract view:'''
# Compute a critical subgraph <math>G'=(V,A')</math> for the input graph <math>G</math>.
# Identify some cycle <math>C</math> in <math>G'</math>.
# Let <math>W</math> denote the minimum weight of all arcs on <math>C</math>.
# For every arc <math>(v,w)\in A</math> pointing from some node <math>v</math> outside <math>C</math> to some node <math>w</math> on <math>C</math>:
##Decrease the weight of <math>(v,w)</math> by <math>w(v',w)-W\geq 0</math>, where <math>(v',w)</math> is the incoming arc of <math>w</math> on <math>C</math>.
## If the new weight of <math>(v,w)</math> is not positive, remove <math>(v,w)</math> from <math>G</math>.
# Shrink <math>C</math> into one new super-node, where every arc pointing to (resp., from) some node on <math>C</math> now points to (from) that super-node.
# Call the algorithm recursively for the modified weighted graph after shrinking, giving branching <math>B</math>.
# Unshrink the graph.
# Add all arcs of <math>C</math> to <math>B</math> giving <math>B'</math>.
# If <math>B</math> contains an arc <math>(v,w)</math> such that <math>v</math> is outside <math>C</math> and <math>w</math> is on <math>C</math>: remove the incoming arc of <math>w</math> on <math>C</math> from <math>B</math>; otherwise, remove one arc with weight <math>W</math> on <math>C</math>. Let <math>B''</math> be the result in both cases.
# Return <math>B''</math>.

'''Proof:'''
Obviously, <math>B''</math> is a branching, so we have to prove that it has maximum weight among all branchings in <math>G</math>. Let <math>B_{\mathrm{opt}}</math> be a maximum branching in <math>G</math> such that, among all maximum branchings in <math>G</math>, <math>B_{\mathrm{opt}}</math> shares as many arcs as possible with <math>B''</math>.

Let <math>C'</math> be a cycle of <math>G'</math> (the case <math>C'=C</math> not excluded). First we show that <math>B_{\mathrm{opt}}</math> contains all arcs of <math>C'</math> except one. So, suppose for a contradiction that <math>B_{\mathrm{opt}}</math> does not contain some of the arcs of <math>C'</math>, say, <math>(v_1,w_1),\ldots,(v_k,w_k)</math> with <math>k>1</math>.

Replacing the incoming arc of any <math>w_i</math> by <math>(v_i,w_i)</math> in <math>B_{\mathrm{opt}}</math> and doing nothing else, would not decrease the total weight. Since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>, such a replacement cannot result in a branching anymore. Since the indegrees do not change by that replacement, this means that adding <math>(v_i,w_i)</math> to <math>B_{\mathrm{opt}}</math> would close a cycle. In other words, there is a path <math>p_i</math> in <math>B_{\mathrm{opt}}</math> from <math>w_i</math> to <math>v_i</math>. Each path <math>p_i</math> must enter <math>C</math> at one of the nodes <math>w_j</math> because, otherwise, the node where <math>p_i</math> enters <math>C'</math> had two incoming arcs in <math>B_{\mathrm{opt}}</math>: the incoming arc on <math>C'</math> and the arc over which <math>p_i</math> enters <math>C'</math>. However, this would imply that there is a cycle in the union of all paths <math>p_i</math> plus all arcs of <math>C''</math> '''not''' in <math>\{(v_1,w_1),\ldots,(v_k,w_k)\}</math>. This union is a subset of <math>B_{\mathrm{opt}}</math>, which yields the desired contradiction.

Now we know that <math>B_{\mathrm{opt}}</math> contains all arcs except one on all cycles of <math>G'</math>. Note that, for any node not on a cycle, the incoming branching arc may be freely chosen without any effect on the rest. So, since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>,<math>B_{\mathrm{opt}}</math> and <math>B''</math> agree on all of these choices. Further note that all cycles of <math>G'</math> are node-disjoint. In summary, we may compare <math>B_{\mathrm{opt}}</math> and <math>B'</math> on each cycle of <math>G'</math> separately.

For <math>C</math>, complete agreement between <math>B_{\mathrm{opt}}</math> and <math>B''</math> follows from the observation that the choice of incoming arcs for all nodes on <math>C</math> is optimal in <math>B''</math> due to the specific modification of the arc weights. And for all other cycles of <math>G'</math>, complete agreement follows from the induction hypothesis. In both cases, we again used the specific choice of <math>B_{\mathrm{opt}}</math> to be as close to <math>B''</math> as possible.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}((n+m)\cdot n)</math> in the worst case, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
Using [[Depth-first search|DFS]] for cycle detection, each recursive step requires <math>\mathcal{O}(n+m)</math>. In each shrink operation, the number of nodes decreases, so the recursion depth is <math>\mathcal{O}(n)</math>.

'''Remark:'''
More sophisticated implementations of this algorithm yield better asymptotic complexities.

== Remarks ==

# The unshrink operation requires that the shrink operation performs some bookkeeping: For the super-node, a cyclically ordered sequence of all nodes and arcs on <math>C</math> (or an equivalent bulk of information) must be attached to a super-node.
# Several cycles may be discovered simultaneously by one run of [[Depth-first search|DFS]]. Note that all cycles in a critical graph are node-disjoint, because no node has more than one incoming arc. Therefore, several cycles may be handled in the same recursive call, without any interference.

Branching by Edmonds

2014-11-27T10:57:13Z

Mahn89: /* Recursive step */

== Abstract view ==

'''Algorithmic problem:''' [[Maximum branching]]

'''Definition:'''
# An arc <math>(v,w)\in A</math> is '''critical''' for <math>w\in V</math> if its weight is not smaller than the weight of any other incoming arc of <math>w</math>.
# A '''critical subgraph''' <math>G'=(V,A')</math> of <math>G</math> contains exactly one incoming arc <math>(v,w)\in A</math> for each node <math>w\in V</math> of positive indegree, where <math>(v,w)</math> is critical.

'''Type of algorithm:''' recursion

'''Invariant:''' The output of a recursive call is a maximum branching of the weighted graph that was the input for this recursive call.

== Recursion anchor ==

'''Abstract view:''' Terminate if <math>G'</math> is cycle-free.

'''Proof:'''
If <math>G'</math> is cycle-free, it is a branching. Consider some other branching <math>B</math>. We have to show that <math>B</math> does not have more total weight than <math>G'</math>.

By definition, a critical graph contains one incoming arc for each node that does have incoming arcs. Therefore, for each arc <math>a</math> of <math>B</math>, there is an arc <math>a'</math> in <math>G'</math> pointing to the same node. Due to the choice of arcs for <math>G'</math>, it is <math>w(a)\leq w(a')</math>.

== Recursive step ==
[[File:Edmonds max branching ani.gif|350px|thumb|right|''animated gif:'' Branching by Edmonds]]
'''Abstract view:'''
# Compute a critical subgraph <math>G'=(V,A')</math> for the input graph <math>G</math>.
# Identify some cycle <math>C</math> in <math>G'</math>.
# Let <math>W</math> denote the minimum weight of all arcs on <math>C</math>.
# For every arc <math>(v,w)\in A</math> pointing from some node <math>v</math> outside <math>C</math> to some node <math>w</math> on <math>C</math>:
##Decrease the weight of <math>(v,w)</math> by <math>w(v',w)-W\geq 0</math>, where <math>(v',w)</math> is the incoming arc of <math>w</math> on <math>C</math>.
## If the new weight of <math>(v,w)</math> is not positive, remove <math>(v,w)</math> from <math>G</math>.
# Shrink <math>C</math> into one new super-node, where every arc pointing to (resp., from) some node on <math>C</math> now points to (from) that super-node.
# Call the algorithm recursively for the modified weighted graph after shrinking, giving branching <math>B</math>.
# Unshrink the graph.
# Add all arcs of <math>C</math> to <math>B</math> giving <math>B'</math>.
# If <math>B</math> contains an arc <math>(v,w)</math> such that <math>v</math> is outside <math>C</math> and <math>w</math> is on <math>C</math>: remove the incoming arc of <math>w</math> on <math>C</math> from <math>B</math>; otherwise, remove one arc with weight <math>W</math> on <math>C</math>. Let <math>B''</math> be the result in both cases.
# Return <math>B''</math>.

'''Proof:'''
Obviously, <math>B''</math> is a branching, so we have to prove that it has maximum weight among all branchings in <math>G</math>. Let <math>B_{\mathrm{opt}}</math> be a maximum branching in <math>G</math> such that, among all maximum branchings in <math>G</math>, <math>B_{\mathrm{opt}}</math> shares as many arcs as possible with <math>B''</math>.

Let <math>C'</math> be a cycle of <math>G'</math> (the case <math>C'=C</math> not excluded). First we show that <math>B_{\mathrm{opt}}</math> contains all arcs of <math>C'</math> except one. So, suppose for a contradiction that <math>B_{\mathrm{opt}}</math> does not contain some of the arcs of <math>C'</math>, say, <math>(v_1,w_1),\ldots,(v_k,w_k)</math> with <math>k>1</math>.

Replacing the incoming arc of any <math>w_i</math> by <math>(v_i,w_i)</math> in <math>B_{\mathrm{opt}}</math> and doing nothing else, would not decrease the total weight. Since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>, such a replacement cannot result in a branching anymore. Since the indegrees do not change by that replacement, this means that adding <math>(v_i,w_i)</math> to <math>B_{\mathrm{opt}}</math> would close a cycle. In other words, there is a path <math>p_i</math> in <math>B_{\mathrm{opt}}</math> from <math>w_i</math> to <math>v_i</math>. Each path <math>p_i</math> must enter <math>C</math> at one of the nodes <math>w_j</math> because, otherwise, the node where <math>p_i</math> enters <math>C'</math> had two incoming arcs in <math>B_{\mathrm{opt}}</math>: the incoming arc on <math>C'</math> and the arc over which <math>p_i</math> enters <math>C'</math>. However, this would imply that there is a cycle in the union of all paths <math>p_i</math> plus all arcs of <math>C''</math> '''not''' in <math>\{(v_1,w_1),\ldots,(v_k,w_k)\}</math>. This union is a subset of <math>B_{\mathrm{opt}}</math>, which yields the desired contradiction.

Now we know that <math>B_{\mathrm{opt}}</math> contains all arcs except one on all cycles of <math>G'</math>. Note that, for any node not on a cycle, the incoming branching arc may be freely chosen without any effect on the rest. So, since <math>B_{\mathrm{opt}}</math> is as close as possible to <math>B''</math>,<math>B_{\mathrm{opt}}</math> and <math>B''</math> agree on all of these choices. Further note that all cycles of <math>G'</math> are node-disjoint. In summary, we may compare <math>B_{\mathrm{opt}}</math> and <math>B'</math> on each cycle of <math>G'</math> separately.

For <math>C</math>, complete agreement between <math>B_{\mathrm{opt}}</math> and <math>B''</math> follows from the observation that the choice of incoming arcs for all nodes on <math>C</math> is optimal in <math>B''</math> due to the specific modification of the arc weights. And for all other cycles of <math>G'</math>, complete agreement follows from the induction hypothesis. In both cases, we again used the specific choice of <math>B_{\mathrm{opt}}</math> to be as close to <math>B''</math> as possible.

== Complexity ==

'''Statement:'''
The asymptotic complexity is in <math>\mathcal{O}((n+m)\cdot n)</math> in the worst case, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
Using [[Depth-first search|DFS]] for cycle detection, each recursive step requires <math>\mathcal{O}(n+m)</math>. In each shrink operation, the number of nodes decreases, so the recursion depth is <math>\mathcal{O}(n)</math>.

'''Remark:'''
More sophisticated implementations of this algorithm yield better asymptotic complexities.

== Remarks ==

# The unshrink operation requires that the shrink operation performs some bookkeeping: For the super-node, a cyclically ordered sequence of all nodes and arcs on <math>C</math> (or an equivalent bulk of information) must be attached to a super-node.
# Several cycles may be discovered simultaneously by one run of [[Depth-first search|DFS]]. Note that all cycles in a critical graph are node-disjoint, because no node has more than one incoming arc. Therefore, several cycles may be handled in the same recursive call, without any interference.

File:Edmonds max branching ani.gif

2014-11-27T09:47:04Z

Mahn89:

Max-Flow Problems

2014-11-25T14:38:04Z

Mahn89: /* Generalizations */

== Basic definitions ==

# [[Basic graph definitions]]
# [[Basic flow definitions]]

== Standard version ==

'''Input:'''
# A directed graph <math>G=(V,A)</math>.
# A '''source node''' <math>s\in V</math> and a '''target (a.k.a. sink) node''' <math>t\in V</math>.
# A nonnegative '''upper bound (a.k.a. capacity)''' <math>u(a)</math> for each arc <math>a\in A</math>.

'''Output:'''
A [[Basic flow definitions#Feasible flow|feasible <math>(s,t)</math>-flow]] that has maximum [[Basic flow definitions#Flow value|flow value]] among all feasible <math>(s,t)</math>-flows.

== Known algorithms ==

# [[Ford-Fulkerson]]
# [[Edmonds-Karp]]
# [[Ahuja-Orlin]]
# [[Dinic]]
# [[Preflow-push]]
# [[FIFO preflow-push]]
# [[Preflow-push with excess scaling]]

== Generalizations ==

# For each arc <math>a\in A</math>, there is a '''lower bound''' <math>\ell(a)</math>, and <math>f(a)\geq\ell(a)</math> is additionally required. The lower bounds need not be nonnegative, so the flow values need not be nonnegative, either. This version is often called '''maximum flow with edge demands'''. It may be reduced to solving two instances of the standard version as follows:
## First, we construct a new graph <math>G'=(V',A')</math> as follows: We add a super-source <math>s'</math> and a super-target <math>t'</math> to <math>V</math>. Next, for every node <math>v\in V</math>, we add an arc <math>(s,v)</math> and an arc <math>(v,t)</math> to <math>A</math>. Finally we add an arc <math>(t,s)</math> to <math>A</math>, if not in <math>A</math> yet.
## For all arcs <math>a\in A</math>, we set <math>\ell'(a):=0</math>. For each node <math>v\in V</math>, we set
##:<math>u'(s,v):=\sum_{(w,v)\in A}\ell(w,v)</math> and <math>u'(v,t):=\sum_{(v,w)\in A} \ell(v,w)</math>.
##:For all arcs <math>a\in A</math>, we set <math>u'(a):=u(a)-\ell(a)</math>. Finally, we set <math>u'(t,s):=+\infty</math>.
## It is easy to see that there is a feasible <math>(s,t)</math>-flow <math>f</math> in <math>G</math> with respect to <math>\ell</math> and <math>u</math> if, and only if, all arcs <math>(s',\cdot)</math> and <math>(\cdot,t')</math> are saturated. This the case if, and only if, the maximum flow <math>f'</math> in <math>G</math> from <math>s'</math> to <math>t'</math> with respect to <math>\ell'</math> and <math>u'</math> yields a flow of value <math>\sum_{a\in A}\ell(a)</math>.
## More specifically, for <math>(v,w)\in A</math>, we set <math>f(v,w):=f'(v,w)+\ell(v,w)</math>.[[File:Maxflowmultiplesource.png|350px|thumb|right|Max-Flow Problem with several sources and targets]]
# More than one source and more than one target can be reduced to the standard version by adding a super-source node <math>s</math>, a super-target node <math>t</math>, an arc <math>(s,v)</math> with "infinite" capacity for each source <math>v</math>, and an arc <math>(v,t)</math> with "infinite" capacity for each target <math>v</math> (for example, the sum of the upper bounds of all arcs is sufficiently large to serve as "infinity").
# Usually, the term '''generalized flow''' is reserved for the specific generalization in which for each node <math>v\in V\setminus\{s,t\}</math>, the ratio of the total sum of all incoming flow an the total sum of all outgoing flow is given (in the standard version, this ratio is 1 due to the flow conservation condition).
# The max-flow problem asks for an optimal steady-state flow. However, in many applications, a certain amount of flow is to be sent as soon as possible from the source to the target. It is easy to see that, if the amount of flow is sufficiently large, then an optimal solution is constant most of the time, and the maximum steady-state flow is this constant flow.

File:Maxflowmultiplesource.png

2014-11-25T14:36:06Z

Mahn89:

Eulerian cycle

2014-11-12T20:57:01Z

Mahn89: /* Historical Approach */

== Definition ==

# A '''eulerian cycle''' is an [[Basic graph definitions#Cycles|ordinary cycle]] in a directed or undirected graph that contains each edge/arc exactly once.
# A directed or undirected graph is called '''eulerian''' if it admits a eulerian cycle.

'''Remark:'''
It is easy to see (and follows from the [[Classical eulerian cycle algorithm|classical algorithm]]) that a graph <math>G</math> is eulerian if, and only if:
# Undirected case: <math>G</math> is connected, and each node has even degree.
# Directed case: <math>G</math> is strongly connected, and for each node <math>v</math>, the indegree of <math>v</math> equals the outdegree of <math>v</math>.

== Input ==

A strongly connected directed or connected undirected graph.

== Output ==

A eulerian cycle as an alternating sequence of nodes and edges/arcs or, alternatively, the (correct) message that the graph is not eulerian.

== Known algorithms ==

[[Classical eulerian cycle algorithm]]

== Historical Approach ==

The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and prefigured the idea of topology. The problem was to find a walk through the city that would cross each bridge once and only once. Euler reformulate the problem in abstracts terms and so he replaces each land mass with an abstract node, aka ''vertex'', and each brigde with an abstract connection, aka ''edge''.
[[File:Eulerkonigsberg.png]]

Euler observes that during any walk in the graph, the number of times one enters a vertex equals the number of times one leaves it. It follows that, for every vertex (except start and finish), the number of edges touches that vertex must be even. With this studies, Euler shows that a necessary condition for an ''Eulerian walk'' is that
* the graph is connected and
* have exactly zero or two nodes of odd degree.

Eulerian cycle

2014-11-12T20:37:42Z

Mahn89: /* Historical Approach */

File:Eulerkonigsberg.png

2014-11-12T20:35:27Z

Mahn89:

Eulerian cycle

2014-11-12T19:37:22Z

Mahn89:

Eulerian cycle

2014-11-12T19:01:11Z

Mahn89: /* Historical Approach */

== Definition ==

# A '''eulerian cycle''' is an [[Basic graph definitions#Cycles|ordinary cycle]] in a directed or undirected graph that contains each edge/arc exactly once.
# A directed or undirected graph is called '''eulerian''' if it admits a eulerian cycle.

'''Remark:'''
It is easy to see (and follows from the [[Classical eulerian cycle algorithm|classical algorithm]]) that a graph <math>G</math> is eulerian if, and only if:
# Undirected case: <math>G</math> is connected, and each node has even degree.
# Directed case: <math>G</math> is strongly connected, and for each node <math>v</math>, the indegree of <math>v</math> equals the outdegree of <math>v</math>.

== Input ==

A strongly connected directed or connected undirected graph.

== Output ==

A eulerian cycle as an alternating sequence of nodes and edges/arcs or, alternatively, the (correct) message that the graph is not eulerian.

== Known algorithms ==

[[Classical eulerian cycle algorithm]]

== Historical Approach ==

The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and prefigured the idea of topology. The problem was to find a walk through the city that would cross each bridge once and only once. Euler reformulate the problem in abstracts terms. So Euler replaces each land mass with an abstract node, aka ''vertex'', and each brigde with an abstract connection, aka ''edge''.
TBC...

Eulerian cycle

2014-11-12T14:52:47Z

Mahn89:

== Definition ==

# A '''eulerian cycle''' is an [[Basic graph definitions#Cycles|ordinary cycle]] in a directed or undirected graph that contains each edge/arc exactly once.
# A directed or undirected graph is called '''eulerian''' if it admits a eulerian cycle.

'''Remark:'''
It is easy to see (and follows from the [[Classical eulerian cycle algorithm|classical algorithm]]) that a graph <math>G</math> is eulerian if, and only if:
# Undirected case: <math>G</math> is connected, and each node has even degree.
# Directed case: <math>G</math> is strongly connected, and for each node <math>v</math>, the indegree of <math>v</math> equals the outdegree of <math>v</math>.

== Input ==

A strongly connected directed or connected undirected graph.

== Output ==

A eulerian cycle as an alternating sequence of nodes and edges/arcs or, alternatively, the (correct) message that the graph is not eulerian.

== Known algorithms ==

[[Classical eulerian cycle algorithm]]

== Historical Approach ==

The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and prefigured the idea of topology. The problem was to find a walk through the city that would cross each bridge once and only once. Euler reformulate the problem in abstracts terms (laying the foundation of ''graph theory''). So Euler replaces each land mass with an abstract node, aka ''vertex'', and each brigde with an abstract connection, aka ''edge''.
TBC...

Eulerian cycle

2014-11-12T14:51:48Z

Mahn89:

== Definition ==

# A '''eulerian cycle''' is an [[Basic graph definitions#Cycles|ordinary cycle]] in a directed or undirected graph that contains each edge/arc exactly once.
# A directed or undirected graph is called '''eulerian''' if it admits a eulerian cycle.

'''Remark:'''
It is easy to see (and follows from the [[Classical eulerian cycle algorithm|classical algorithm]]) that a graph <math>G</math> is eulerian if, and only if:
# Undirected case: <math>G</math> is connected, and each node has even degree.
# Directed case: <math>G</math> is strongly connected, and for each node <math>v</math>, the indegree of <math>v</math> equals the outdegree of <math>v</math>.

== Input ==

A strongly connected directed or connected undirected graph.

== Output ==

A eulerian cycle as an alternating sequence of nodes and edges/arcs or, alternatively, the (correct) message that the graph is not eulerian.

== Known algorithms ==

[[Classical eulerian cycle algorithm]]

== Historical Approach ==

The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and prefigured the idea of topology. The problem was to find a walk through the city that would cross each bridge once and only once. Euler reformulate the oriblem in abstracts terms (laying the foundation of ''graph theory''). So Euler replaces each land mann with an abstract node, aka ''vertex'', and each brigde with an abstract connection, aka ''edge''.
TBC...

Sorting Algorithms

2014-11-12T14:21:33Z

Mahn89:

== General Information ==

The sorting problem is one of the most frequent algorthmic problems. Its simplest form is to sort a finit set of numbers ascending or descending.

Instead of numbers you can sort any data, e.g. strings. There must be a relation between the elements of the set, so to say, an ordering relation <math> \leq </math> has to be defined.

Often, the data is a set of complex data types, that has to be sorted by a special criteria. For example you have a set of person descriptions to be sorted by the birth dates.

== Definition ==
Let <math>n \in \N</math> and <math>a = a_0, \dots, a_{n-1}</math> a finit sequence with <math>a_i \in \N \quad (i = 0, \dots, n-1)</math>

The ''sorting problem'' is to find a sequence <math>a_{\varphi (0)}, \dots, a_{\varphi (n-1)}</math> with folloing constraints:
:* <math>a_{\varphi(i)} \leq a_{\varphi(j)} \quad \forall i,j \in \{0, \dots, n-1\}, i < j</math>
:* the mapping <math>\varphi</math> is a permutation of the index set <math>\{0, \dots, n-1\}</math>

== Example ==
Let <math>n = 8</math> and <math>a = 3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6</math>
:{|
|style="width: 4em"| <math>i:</math> || <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
|-
| <math>a_i:</math> || <math>3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6</math>
|-
| <math>\varphi(i):</math> || <math>2 \ 6 \ 5 \ 0 \ 4 \ 3 \ 7 \ 1</math>
|-
| <math>a_{\varphi(i)}:</math> || <math>1 \ 2 \ 3 \ 3 \ 3 \ 4 \ 6 \ 8</math>
|}

== Important algorithms ==
* [[Bogosort]]
* [[Bubble]]
* [[Bubblesort]]
* [[Bucketsort]]
* [[Insertion sort]]
* [[Mergesort]]
* [[Quicksort]]
* [[Selection sort]]

Sorting Algorithms

2014-11-10T14:29:21Z

Mahn89:

== General information ==

The sorting problem is one of the most frequent algorthmic problems. Its simplest form is to sort a finit set of numbers ascending or descending.

Instead of numbers you can sort any data, e.g. strings. There must be a relation between the elements of the set, so to say, an ordering relation <math> \leq </math> has to be defined.

Often, the data is a set of complex data types, that has to be sorted by a special criteria. For example you have a set of person descriptions to be sorted by the birth dates.

== Definition ==
Let <math>n \in \N</math> and <math>a = a_0, \dots, a_{n-1}</math> a finit sequence with <math>a_i \in \N \quad (i = 0, \dots, n-1)</math>

The ''sorting problem'' is to find a sequence <math>a_{\varphi (0)}, \dots, a_{\varphi (n-1)}</math> with folloing constraints:
:* <math>a_{\varphi(i)} \leq a_{\varphi(j)} \quad \forall i,j \in \{0, \dots, n-1\}, i < j</math>
:* the mapping <math>\varphi</math> is a permutation of the index set <math>\{0, \dots, n-1\}</math>

== Example ==
Let <math>n = 8</math> and <math>a = 3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6</math>
:{|
|style="width: 4em"| <math>i:</math> || <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
|-
| <math>a_i:</math> || <math>3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6</math>
|-
| <math>\varphi(i):</math> || <math>2 \ 6 \ 5 \ 0 \ 4 \ 3 \ 7 \ 1</math>
|-
| <math>a_{\varphi(i)}:</math> || <math>1 \ 2 \ 3 \ 3 \ 3 \ 4 \ 6 \ 8</math>
|}

== Important algorithms ==
* [[Bogosort]]
* [[Bubble]]
* [[Bubblesort]]
* [[Bucketsort]]
* [[Insertion sort]]
* [[Mergesort]]
* [[Quicksort]]
* [[Selection sort]]

Quicksort

2014-11-09T15:32:28Z

Mahn89: /* Complexity */

[[Category:Sorting Algorithms]]
[[Category:Divide and Conquer]]
<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">Quick Sort</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/quick-sort-1945 Openlearnware]</div>
</div>

== General information ==
'''Algorithmic problem:''' [[Sorting based on pairwise comparison]]

'''Type of algorithm:''' recursion

== Abstract view ==

'''Invariant:''' After a recursive call, the input sequence of this recursive call is sorted.

'''Variant:''' In each recursive call, the sequence of the callee is strictly shorter than that of the caller.

'''Break condition:''' The sequence is empty or a singleton.

== Induction basis ==

'''Abstract view:''' Nothing to do on an empty sequence or a singleton.

'''Implementation:''' Ditto.

'''Proof:''' Empty sequences and singletons are trivially sorted.

== Induction step ==

=== Abstract view: ===
# Choose a pivot value <math>p \in [min\{x|x \in S\},\dots,max\{x|x \in S\}]</math> (note that <math>p</math> is not required to be an element of <math>S</math>.
# Partition <math>S</math> into sequences, <math>S_1</math>, <math>S_2</math> and <math>S_3</math>, such that <math>x < p</math> for all <math>x \in S_1</math>, <math>x = p</math> for all <math>x \in S_2</math>, and <math>x > p</math> for all <math>x \in S_3</math>.
# Sort <math>S_1</math> and <math>S_3</math> recursively.
# The concatenation of all three lists, <math>S_1 \| S_2 \| S_3</math>, is the result of the algorithm.

=== Implementation: ===

# Chose <math>p \in [min\{x|x \in S\},\dots,max\{x|x \in S\}]</math> according to some pivoting rule.
# <math>S_1 := S_2 := S_3 := \emptyset</math>.
# For all <math>x \in S</math>, append <math>x</math> to
## <math>S_1</math> if <math>x < p</math>,
## <math>S_2</math> if <math>x = p</math>,
## <math>S_3</math> if <math>x > p</math>.
# Call Quicksort on <math>S_1</math> giving <math>S_1'</math>
# Call Quicksort on <math>S_3</math> giving <math>S_3'</math>
# Return <math>S_1' \| S_2' \| S_3'</math>.

=== Correctness: ===

By induction hypothesis, <math>S_1'</math> and <math>S_3'</math> are sorted permutations of <math>S_1</math> and <math>S_3</math>, respectively. In particular <math>S_1' \| S_2 \| S_3'</math> is a permutation of <math>S</math>. To see that this permutation is sorted, let <math>x</math> and <math>y</math> be two members of <math>S</math> such that <math>y</math> immediately succeeds <math>x</math> in the resulting sequence <math>S_1' \| S_2 \| S_3'</math>. We have to show <math>x \leq y</math>.
# If <math>x,y \in S_1'</math> or <math>x,y \in S_3'</math>, <math>x \leq y</math> resultes from the induction hypothesis.
# On the other hand, if <math>x,y \in S_2</math>. It is <math>x = y = p</math>, which trivially implies <math>x \leq y</math>
# Finally, for following cases, <math>x \leq y</math> is implied by the specific way of partitioning <math>S</math> into <math>S_1'</math>, <math>S_2</math> and <math>S_3'</math>:
## <math>x \in S_1'</math> and <math>y \in S_2</math>
## <math>x \in S_2</math> and <math>y \in S_3'</math>
## <math>x \in S_1'</math> and <math>y \in S_3'</math>

Obviously, this case distinction covers all potential cases, so the claim is proved.

== Complexity ==

=== Statement: ===
[[File:Quicksortrecursion.png|350px|thumb|right|recursion depth of quick sort : [A] best case, [B] avg. case, [C] worst case]]
In the worst case, the complexity is <math>\Theta(n^2)</math>.

If the pivot rule ensures for some <math>\alpha < 1</math> that the lengths of <math>S_1</math> and <math>S_3</math> are at most <math>\alpha</math> times the size of <math>S</math>, then it is even <math>O(n \log n)</math> in the worst case.

If each pivot value is chosen uniformly randomly from members of the respective sequence and if all selections of pivot values are stochastically independent, the average-case complexity is <math>O(n \log n)</math>.

=== Proof: ===
First note that the complexity for a single recursive call on <math>S</math> (disregarding the complexity for the recursive descents on <math>S_1</math> and <math>S_3</math> is in <math>O(|S|)</math>. On each recursive level, all calls are on distinct subsets of <math>S</math>. Therefore, the number of recursive calls with non-empty sequences on one recursive level is in <math>O(n)</math>. The number of calls with empty sequences on one level is at most twice the total number of calls with non-empty sequences on the previous level. Hence, the number of calls with empty sequences on one recursive level is in <math>O(n)</math> as well. In summary, the total complexity on a recursive level is <math>O(n)</math>. So, for the total complexity, it remains to estimate the number of recursive levels.

Now consider the first statement. The recursion variant implies that the deepest recursive level is <math>O(n)</math>. This gives the claimed <math>O(n^2)</math> in the worst case.

Next assume there is a fixed <math>\alpha < 1</math> such that <math>|S_1| \leq \alpha \cdot|S|</math> and <math>|S_3| \leq \alpha \cdot|S|</math> is guaranteed in each recursive call. Then the length of any sequence on recursive level <math>\#i</math> is at most <math>\alpha ^ i \cdot |S|</math>. Therefore, the maximal recursive depth is <math>\lceil \log_{a-1}(n)\rceil</math>. Since <math>\alpha^{-1} > 1</math>, the total complexity is in <math>O(n \log n)</math> in the worst case.

For the last statement, the average-case analysis, first note that the number of comparisons alone has the same asymptotic complexity as the algorithm as a whole. Next note that any <math>x,y \in S</math> are compared at most once throughout the entire algorithm if, and only if, <math>x</math> or <math>y</math> is chosen as the pivot value for a subsequence to which both elements belong. For <math>x,y \in S</math>, let <math>Pr(x,y)</math> denote the probability that <math>x</math> and <math>y</math> are indeed compared. Since comparison events are distinct and <math>Pr(x,y )\in \{0,1\}</math> for all <math>x,y \in S</math>, the [[Expected value|expected number]] of comparisons is

<math>\sum_{x,y \in S, x \neq y} Pr(x,y)</math>

Let <math>n := |S|</math>, and for <math>i,j \in \{1,\dots,n\}</math>, let <math>Pr(i,j)</math> denote the probability that the <math>i</math>-th and the <math>j</math>-th elemet of the eventual sorted sequence are compared throughout the algorithm. Using this notation, we may rewrite the above summation as follows:

<math>\sum_{x,y \in S, x \neq y} Pr(x,y) = \sum_{i=1}^{n-1} \sum_{j = i+1}^{n} Pr(i,j)</math>.

For <math>i,j \in \{1,\dots,n\}</math>, <math>i < j</math>, let <math> S_{ij}</math> denote the subsequence of the eventual sorted sequence that starts with <math>i</math> and ends with <math>j</math>. The elements <math>\#i</math> and <math>\#j</math> are compared if, and only if, <math>\#i</math> or <math>\#j</math> is the very first element of <math>S_{ij}</math> to be chosen as a pivot. The probability of this event is <math>\frac{2}{|S_{ij}|} = \frac{2}{j - i + 1}</math>, so we obtain

<math>\sum_{i=1}^{n-1} \sum_{j = i+1}^{n} \frac{2}{j-i+1}</math>.

Substituting <math>k := j-i</math>, this gives

<math>\sum_{i=1}^{n-1} \sum_{j = i+1}^{n} \frac{2}{j-i+1} = \sum_{i=1}^{n-1} \sum_{k=1}^{n} \frac{2}{k+1} \leq 2(n - 1)</math>.

<math>\sum_{k=1}^n \frac{1}{k+1} \leq 2(n-1)</math>.

<math>\sum_{k+1}^n \frac{1}{k}</math>.

The [http://en.wikipedia.org/wiki/Harmonic_series_(mathematics)#Rate_of_divergence asymptotic behavior] of the [http://en.wikipedia.org/wiki/Harmonic_series_(mathematics) harmonic series] is <math>\Theta(\log n)</math>, so the last expression is <math>\Theta(n \log n)</math>.

== Further information ==

If <math>S</math> is an array, <math>S</math> cannot be decomposed into subsequences. We would liko to avoid the need for additional arrays and copy operations. Instead, the array should be sorted in-place, that is, by swap operations on pairs of elements. The auxiliary procedure, [[Pivot partitioning by scanning]], is designed exactly for that: it permutes the array such that each of <math>S_1</math> and <math>S_2</math> is a subarray. Then each recursive call of Quicksort operates on a subarray of the input array, which is specified by two index pointers.

File:Quicksortrecursion.png

2014-11-09T15:28:42Z

Mahn89:

Sorting Algorithms

2014-11-09T14:18:14Z

Mahn89:

== General information ==

The sorting problem is one of the most frequent algorthmic problems. Its simplest form is to sort a finit set of numbers ascending or descending.

Instead of numbers you can sort any data, e.g. string. There must be a relation between the elements of the set, so to say, an ordering relation <math> \leq </math> has to be defined.

Often, the data is a set of complex data types, that has to be sorted by a special criteria. For example you have a set of person descriptions to be sorted by the birth dates.

== Definition ==
Let <math>n \in \N</math> and <math>a = a_0, \dots, a_{n-1}</math> a finit sequence with <math>a_i \in \N \quad (i = 0, \dots, n-1)</math>

The ''sorting problem'' is to find a sequence <math>a_{\varphi (0)}, \dots, a_{\varphi (n-1)}</math> with folloing constraints:
:* <math>a_{\varphi(i)} \leq a_{\varphi(j)} \quad \forall i,j \in \{0, \dots, n-1\}, i < j</math>
:* the mapping <math>\varphi</math> is a permutation of the index set <math>\{0, \dots, n-1\}</math>

== Example ==
Let <math>n = 8</math> and <math>a = 3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6</math>
:{|
|style="width: 4em"| <math>i:</math> || <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
|-
| <math>a_i:</math> || <math>3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6</math>
|-
| <math>\varphi(i):</math> || <math>2 \ 6 \ 5 \ 0 \ 4 \ 3 \ 7 \ 1</math>
|-
| <math>a_{\varphi(i)}:</math> || <math>1 \ 2 \ 3 \ 3 \ 3 \ 4 \ 6 \ 8</math>
|}

== Important algorithms ==
* [[Bogosort]]
* [[Bubble]]
* [[Bubblesort]]
* [[Bucketsort]]
* [[Insertion sort]]
* [[Mergesort]]
* [[Quicksort]]
* [[Selection sort]]

Sorting Algorithms

2014-11-09T11:45:54Z

Mahn89:

== General information ==

The sorting problem is one of the most frequent algorthmic problems. Its simplest form is to sort a finit set of numbers ascending or descending.

Instead of numbers you can sort any data, e.g. string. There must be a relation between the elements of the set, so to say, an ordering relation <math> \leq </math> has to be defined.

Often, the data is a set of complex data types, that has to be sorted by a special criteria. For example you have a set of person descriptions to be sorted by the birth dates.

== Definition ==
Let <math>n \in \N</math> and <math>a = a_0, \dots, a_{n-1}</math> a finit sequence with <math>a_i \in \N \quad (i = 0, \dots, n-1)</math>

The ''sorting problem'' is to find a sequence <math>a_{\varphi (0)}, \dots, a_{\varphi (n-1)}</math> with folloing constraints:
:* <math>a_{\varphi(i)} \leq a_{\varphi(j)} \quad \forall i,j \in \{0, \dots, n-1\}, i < j</math>
:* the mapping <math>\varphi</math> is a permutation of the index set <math>\{0, \dots, n-1\}</math>

== Example ==
Let <math>n = 8</math> and <math>a = 3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6</math>
:{|
|style="width: 4em"| <math>i:</math> || <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
|-
| <math>a_i:</math> || <math>3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6</math>
|-
| <math>\varphi(i):</math> || <math>2 \ 6 \ 5 \ 0 \ 4 \ 3 \ 7 \ 1</math>
|-
| <math>a_{\varphi(i)}:</math> || <math>1 \ 2 \ 3 \ 3 \ 3 \ 4 \ 6 \ 8</math>
|}

Sorting Algorithms

2014-11-09T11:39:21Z

Mahn89:

== General information ==

The sorting problem is one of the most frequent algorthmic problems. Its simplest form is to sort a finit set of numbers ascending or descending.

Instead of numbers you can sort any data, e.g. string. There must be a relation between the elements of the set, so to say, an ordering relation <math> \leq </math> has to be defined.

Often, the data is a set of complex data types, that has to be sorted by a special criteria. For example you have a set of person descriptions to be sorted by the birth dates.

== Definition ==
Let <math>n \in \N</math> and <math>a = a_0, \dots, a_{n-1}</math> a finit sequence with <math>a_i \in \N \quad (i = 0, \dots, n-1)</math>

The ''sorting problem'' is to find a sequence <math>a_{\varphi (0)}, \dots, a_{\varphi (n-1)}</math> with folloing constraints:
:* <math>a_{\varphi(i)} \leq a_{\varphi(j)} \quad \forall i,j \in \{0, \dots, n-1\}, i < j</math>
:* the mapping <math>\varphi</math> is a permutation of the index set <math>\{0, \dots, n-1\}</math>

== Example ==
Let <math>n = 8</math> and <math>a = 3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6</math>
:{|
| <math>i:</math> || <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
|-
| <math>a_i:</math> || <math>3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6</math>
|-
| <math>\varphi(i):</math> || <math>2 \ 6 \ 5 \ 0 \ 4 \ 3 \ 7 \ 1</math>
|-
| <math>a_{\varphi(i)}:</math> || <math>1 \ 2 \ 3 \ 3 \ 3 \ 4 \ 6 \ 8</math>
|}

Sorting Algorithms

2014-11-09T11:34:22Z

Mahn89:

== General information ==

The sorting problem is one of the most frequent algorthmic problems. Its simplest form is to sort a finit set of numbers ascending or descending.

Instead of numbers you can sort any data, e.g. string. There must be a relation between the elements of the set, so to say, an ordering relation <math> \leq </math> has to be defined.

Often, the data is a set of complex data types, that has to be sorted by a special criteria. For example you have a set of person descriptions to be sorted by the birth dates.

== Definition ==
Let <math>n \in \N</math> and <math>a = a_0, \dots, a_{n-1}</math> a finit sequence with <math>a_i \in \N \quad (i = 0, \dots, n-1)</math>

The ''sorting problem'' is to find a sequence <math>a_{\varphi (0)}, \dots, a_{\varphi (n-1)}</math> with folloing constraints:
:* <math>a_{\varphi(i)} \leq a_{\varphi(j)} \quad \forall i,j \in \{0, \dots, n-1\}, i < j</math>
:* the mapping <math>\varphi</math> is a permutation of the index set <math>\{0, \dots, n-1\}</math>

== Example ==
Let <math>n = 8</math> and <math>a = 3 \ 8 \ 1 \ 4 \ 3 \ 3 \ 2 \ 6</math>
{|
| <math>i:</math>
| <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
|-
| <math>a_i:</math>
| <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
|-
| <math>\varphi(i):</math>
| <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
|-
| <math>a_{\varphi(i)}:</math>\quad
| <math>0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7</math>
|
|}

Sorting Algorithms

2014-11-09T10:53:19Z

Mahn89: Created page with "== General information == The sorting problem is one of the most frequent algorthmic problems. Its simplest form is to sort a finit set of numbers ascending or descending. I..."

Strongly connected components

2014-10-23T15:55:53Z

Mahn89:

== Definition ==
[[File:Scc.png|300px|thumb|right|Graph with marked strongly connected components]]
Let <math>G=(V,A)</math> be a [[Basic graph definitions|directed graph]]. Consider the following equivalence relation on the nodes: <math>v\in V</math> and <math>w\in V</math> are equivalent if, and only if, there is a path from <math>v</math> to <math>w</math> and a path from <math>w</math> to <math>v</math> in <math>G</math>. The equivalence classes are called the '''strongly connected components (SCC)''' of <math>G</math>.

== Input ==

A [[Basic graph definitions|directed graph]] <math>G=(V,A)</math>.

== Output ==

A set of sets of nodes. Each set of nodes contains exactly the nodes of one SCC. The correspndence between SCC and sets of nodes is one-to-one.

== Pseudocode ==

====STRONGLY-CONNECTED-COMPONENTS(''D'')====

<code>
STRONGLY-CONNECTED-COMPONENTS(''D'')
1 call '''DFS'''(''D'') to compute finishing times ''f''[v] for each vertex ''v'' ∈ ''V''
2 compute ''D''<sup>''T''</sup> (w.r.t. step 3)
3 call '''DFS'''(''D''<sup>''T''</sup>), but in the main loop of '''DFS''', consider the vertices in order of decreasing ''f''[v] as computed in step 1
4 output the vertices of each tree in the '''DFS''' forest of step 3 as a separate strongly connected component
</code>

== Known algorithms ==

# [[Kosaraju]]

== Further information ==
''STRONGLY-CONNECTED-COMPONENTS'' runs in linear time.

Strongly connected components

2014-10-23T15:54:01Z

Mahn89: /* Definition */

Strongly connected components

2014-10-23T15:51:38Z

Mahn89:

== Definition ==
[[File:Scc.png|300px|thumb|right|Graph with marked strongly connected components]]
Let <math>G=(V,A)</math> be a [[Basic graph definitions|directed graph]]. Consider the following equivalence relation on the nodes: <math>v\in V</math> and <math>w\in V</math> are equivalent if, and only if, there is a path fmo <math>v</math> to <math>w</math> and a path from <math>w</math> to <math>v</math> in <math>G</math>. The equivalence classes are called the '''strongly connected components (SCC)''' of <math>G</math>.

== Input ==

A [[Basic graph definitions|directed graph]] <math>G=(V,A)</math>.

== Output ==

A set of sets of nodes. Each set of nodes contains exactly the nodes of one SCC. The correspndence between SCC and sets of nodes is one-to-one.

== Pseudocode ==

====STRONGLY-CONNECTED-COMPONENTS(''D'')====

<code>
STRONGLY-CONNECTED-COMPONENTS(''D'')
1 call '''DFS'''(''D'') to compute finishing times ''f''[v] for each vertex ''v'' ∈ ''V''
2 compute ''D''<sup>''T''</sup> (w.r.t. step 3)
3 call '''DFS'''(''D''<sup>''T''</sup>), but in the main loop of '''DFS''', consider the vertices in order of decreasing ''f''[v] as computed in step 1
4 output the vertices of each tree in the '''DFS''' forest of step 3 as a separate strongly connected component
</code>

== Known algorithms ==

# [[Kosaraju]]

Dijkstra

2014-10-22T13:04:53Z

Mahn89: /* Further information */

[[Category:Graph Algorithms]]
[[Category:All Pairs Shortest Paths]]
<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>

'''Dijstra's algorithm''' is a graph algortihm solving the single-source shortest-paths problem.

== Requirements ==

* directed Graph <math>G=(V,E)</math>
* weight function <math>w\colon E\to\mathbb R</math>
* <math>\forall(u,v)\in E\colon w(u,v)\geq 0</math>
* source <math>s\in V</math>
* Datastruct <math>S</math>
* Datastruct <math>Q</math>

== General information ==

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

'''Prerequisities:''' For all <math>\alpha \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 \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 = \empty</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 [[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>w</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> belong to <math>V_{i-1}</math>. 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(m+T(n)\cdot n)</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.

== Pseudocode ==

====DIJKSTRA(''G,w,s'')====

<code>
DIJKSTRA(''G,w,s'')
1 INITIALIZE-SINGLE-SOURCE(''G,s'')
2 ''S'' = ∅
3 ''Q'' = ''G.V''
4 '''while''' ''Q'' ≠ ∅
5 ''u'' = EXTRACT-MIN(''Q'')
6 ''S'' = ''S'' ∪ {''u''}
7 '''for''' each vertex ''v'' ∈ G.''Adj''[''u'']
8 RELAX(''u,v,w'')
</code>

====RELAX(''u,v,w'')====
<code>
RELAX(''u,v,w'')
1 '''if''' ''v.d'' > ''u.d'' + ''w''(''u,v'')
2 ''v.d'' = ''u.d'' + ''w''(''u,v'')
3 ''v.π'' = ''u''
</code>

<code>
====INITIALIZE-SINGLE-SOURCE(''G,s'')====
INITIALIZE-SINGLE-SOURCE(''G,s'')
1 '''for''' each vertex ''v'' ∈ ''G.V''
2 ''v.d'' = ∞
3 ''v.π'' = NIL
4 ''s.d'' = 0
</code>

== Further information ==
# 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 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 and [[Paths|admissible distance function]] <math>h:V \to \R</math>, replace length <math>l</math> by <math>l_h</math> where <math>l_h(a) := l(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.

Dijkstra

2014-10-22T13:04:34Z

Mahn89: /* Further information */

[[Category:Graph Algorithms]]
[[Category:All Pairs Shortest Paths]]
<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>

'''Dijstra's algorithm''' is a graph algortihm solving the single-source shortest-paths problem.

== Requirements ==

* directed Graph <math>G=(V,E)</math>
* weight function <math>w\colon E\to\mathbb R</math>
* <math>\forall(u,v)\in E\colon w(u,v)\geq 0</math>
* source <math>s\in V</math>
* Datastruct <math>S</math>
* Datastruct <math>Q</math>

== General information ==

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

'''Prerequisities:''' For all <math>\alpha \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 \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 = \empty</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 [[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>w</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> belong to <math>V_{i-1}</math>. 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(m+T(n)\cdot n)</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.

== Pseudocode ==

====DIJKSTRA(''G,w,s'')====

<code>
DIJKSTRA(''G,w,s'')
1 INITIALIZE-SINGLE-SOURCE(''G,s'')
2 ''S'' = ∅
3 ''Q'' = ''G.V''
4 '''while''' ''Q'' ≠ ∅
5 ''u'' = EXTRACT-MIN(''Q'')
6 ''S'' = ''S'' ∪ {''u''}
7 '''for''' each vertex ''v'' ∈ G.''Adj''[''u'']
8 RELAX(''u,v,w'')
</code>

====RELAX(''u,v,w'')====
<code>
RELAX(''u,v,w'')
1 '''if''' ''v.d'' > ''u.d'' + ''w''(''u,v'')
2 ''v.d'' = ''u.d'' + ''w''(''u,v'')
3 ''v.π'' = ''u''
</code>

<code>
====INITIALIZE-SINGLE-SOURCE(''G,s'')====
INITIALIZE-SINGLE-SOURCE(''G,s'')
1 '''for''' each vertex ''v'' ∈ ''G.V''
2 ''v.d'' = ∞
3 ''v.π'' = NIL
4 ''s.d'' = 0
</code>

== Further information ==
# 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 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 and [[Paths|admissible distance function]] <math>h:V \to \R</math>, replace length <math>l</math> by <math>l_h</math> where <math>l_h(a) := l(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.

File:Dijkstragoaldirected.png

2014-10-22T12:59:23Z

Mahn89: examples for new length in a goal-directed search

examples for new length in a goal-directed search

Dijkstra

2014-10-22T11:48:00Z

Mahn89: /* Further information */

[[Category:Graph Algorithms]]
[[Category:All Pairs Shortest Paths]]
<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>

'''Dijstra's algorithm''' is a graph algortihm solving the single-source shortest-paths problem.

== Requirements ==

* directed Graph <math>G=(V,E)</math>
* weight function <math>w\colon E\to\mathbb R</math>
* <math>\forall(u,v)\in E\colon w(u,v)\geq 0</math>
* source <math>s\in V</math>
* Datastruct <math>S</math>
* Datastruct <math>Q</math>

== General information ==

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

'''Prerequisities:''' For all <math>\alpha \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 \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 = \empty</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 [[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>w</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> belong to <math>V_{i-1}</math>. 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(m+T(n)\cdot n)</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.

== Pseudocode ==

====DIJKSTRA(''G,w,s'')====

<code>
DIJKSTRA(''G,w,s'')
1 INITIALIZE-SINGLE-SOURCE(''G,s'')
2 ''S'' = ∅
3 ''Q'' = ''G.V''
4 '''while''' ''Q'' ≠ ∅
5 ''u'' = EXTRACT-MIN(''Q'')
6 ''S'' = ''S'' ∪ {''u''}
7 '''for''' each vertex ''v'' ∈ G.''Adj''[''u'']
8 RELAX(''u,v,w'')
</code>

====RELAX(''u,v,w'')====
<code>
RELAX(''u,v,w'')
1 '''if''' ''v.d'' > ''u.d'' + ''w''(''u,v'')
2 ''v.d'' = ''u.d'' + ''w''(''u,v'')
3 ''v.π'' = ''u''
</code>

<code>
====INITIALIZE-SINGLE-SOURCE(''G,s'')====
INITIALIZE-SINGLE-SOURCE(''G,s'')
1 '''for''' each vertex ''v'' ∈ ''G.V''
2 ''v.d'' = ∞
3 ''v.π'' = NIL
4 ''s.d'' = 0
</code>

== Further information ==
# 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 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).
# The early termination variant may be modified as follows: for and [[Paths|admissible distance function]] <math>h:V \to \R</math>, replace length <math>l</math> by <math>l_h</math> where <math>l_h(a) := l(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.

File:Dijkstrabidirectional.png

2014-10-22T11:42:59Z

Mahn89: Mahn89 uploaded a new version of "File:Dijkstrabidirectional.png"

comparison of the areas used in a uni-directional case and a bi-directional one

File:Dijkstrabidirectional.png

2014-10-22T11:42:35Z

Mahn89: Mahn89 uploaded a new version of "File:Dijkstrabidirectional.png"

comparison of the areas used in a uni-directional case and a bi-directional one

File:Dijkstrabidirectional.png

2014-10-22T11:41:45Z

Mahn89: Mahn89 uploaded a new version of "File:Dijkstrabidirectional.png"

comparison of the areas used in a uni-directional case and a bi-directional one

File:Dijkstrabidirectional.png

2014-10-22T11:17:17Z

Mahn89: comparison of the areas used in a uni-directional case and a bi-directional one

comparison of the areas used in a uni-directional case and a bi-directional one