Single source shortest paths: Difference between revisions

From Algowiki
Jump to navigation Jump to search
(Created page with "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:1e...")
 
(Replaced content with " == Input == # A directed graph <math>G=(V,A)</math> # an arc weight <math> l(a) \in \mathbb{R}</math> for each arc <math>a \in A</math> # a '''root node''' <math> s \in V...")
Line 1: Line 1:
[[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>
== Input ==
# A directed graph <math>G=(V,A)</math>
# an arc weight <math> l(a) \in \mathbb{R}</math> for each arc <math>a \in A</math>
# a '''root node''' <math> s \in V </math>


<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 ==
== Output ==
'''Algorithmic problem:''' [[Sorting based on pairwise comparison]]
For each <math>v \in V</math>, a real value <math>\delta (v)</math>, the '''length''' of a shortest <math>(s,v)</math>-path in <math>G</math> subject  to <math>l</math>


'''Type of algorithm:''' recursion
== Objective ==
N/A


== 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 ==
== Complexity ==
Polynomial


=== Statement: ===
== Known algorithms ==
In the worst case, the complexity is <math>\Theta(n^2)</math>.
[[Dijkstra]]
 
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.
== Known variants ==

Revision as of 10:28, 20 October 2014

Input

  1. A directed graph [math]\displaystyle{ G=(V,A) }[/math]
  2. an arc weight [math]\displaystyle{ l(a) \in \mathbb{R} }[/math] for each arc [math]\displaystyle{ a \in A }[/math]
  3. a root node [math]\displaystyle{ s \in V }[/math]


Output

For each [math]\displaystyle{ v \in V }[/math], a real value [math]\displaystyle{ \delta (v) }[/math], the length of a shortest [math]\displaystyle{ (s,v) }[/math]-path in [math]\displaystyle{ G }[/math] subject   to [math]\displaystyle{ l }[/math]

Objective

N/A


Complexity

Polynomial

Known algorithms

Dijkstra


Known variants

Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Single_source_shortest_paths&oldid=1388"