Contents

• 00 - Introduction
  • Glossary
• 01 - Stable Matching
• 02 - Analysis of Algorithms
• 03 - Review of Graphs and Priority Queues
• 04 - Linear Time Algoirthms
• 05 - Greedy Algorithms
• 06 - Greedy Graph Algorithms
• 07 - Applications of Minimum Spanning Trees
• 08 - Divide and Conquer Algorithms
• 09 - Dynamic Programming
• 10 - Network Flow
• 11 - Network Flow Applications
• 12 - NP and Computational Tractibility
• 13 - NP-Complete Problems
• 14 - Coping with NP-Completeness
• 15 - Solutions

Introduction

Notes from CS 4104 with exercises and derivations from "Algorithm Design" by Kleinberg and Tardos.

Glossary

01 - Stable Matching

Problem

• Each man ranks all the women in order of preference

• Each woman ranks all the men in order of preference

• Each person uses all ranks from $1, ... , n$ s.t. there are no ties or incomplete lists

Male preference matrix:

Female preference matrix:

• A Matching: each man is paired with ≤ 1 woman and vice versa
• A Perfect Matching: each man is paired with exactly 1 woman and vice versa
  • "perfect" means one-to-one mapping
• A Rogue Couple: a man and a woman who are not matched, but prefer each other to their current partners
• A Stable Matching: A perfect matching without any rogue couples

Solution: Gale-Shapley Algorithm

Proof of Perfection

1. Suppose the set $S$ of pairs returned by Gale-Shapley algorithm is not perfect
2. $S$ is a matching, therefore there must be at least one free man $m$
3. $m$ has proposed to all women (since the algorithm terminated)
4. Therefore, each woman must be engaged (since she remains engaged after the first proposal to her)
5. Therefore, all men must be engaged, contradicting ⚔️ the assumption that $m$ is free
6. That matching is perfect since the program terminated QED.

Proof of Stability

1. Suppose $S$ is not stable i.e. there are two pairs $(m_1, w_1)$, $(m_2, w_2) \in S$ s.t $m_1$ prefers $w_2 > w_1$ and $w_2$ prefers $m_1 > m_2$
2. $m_1$ must have proposed to $w_2$ prior to $w_1$ because at that stage $w_2$ must have rejected $m_1$; otherwise she would have been paired with $w_1$, which would in turn prevent the pairing of $(m_2, w_2)$ in a later iteration
3. When $w_2$ rejected $m_1$, she must have been paired with some man $m_3 > m_1$
4. Since $m_2$ is paired with $w_2$ at termination, $w_2$ must prefer $m_2$ to $m_3$ or $m_2 = m_3$
5. This contradicts ⚔️ our conclusion (from instability) that $w_2$ prefers $m_1 > m_2$ QED.

Observations

• This algorithm computes a matching i.e. each woman gets pair with at most one man and vice versa
• The man's status can alternate between being free and being engaged
• The woman's status remains engaged after the first proposal
• The ranking of a man's partner remains the same or goes down
• The ranking of a woman's partner can never go down
• The number of proposals made after $k$ iterations is the best indicator of progress
• The max number of total proposals (or iterations) that can be made is $n^2$
• Always produces the same matching in which each man is paired with his best, valid partner, but each woman is paired with her worst, valid partner

02 - Analysis of Algorithms

Polynomial Time

• Essentially brute forcing
• e.g. brute force sorting:
  • Given $n$ numbers, permute them so that they appear in increasing order
  • Try all $n!$ permutations
  • For each permutation, check if it is sorted
  • $O(nn!)$
• Desirable scaling property: when the input size doubles, the algorithm should only slow down by some constant $c$
• An algorithm has polynomial running time if there exists constants $c,d > 0$ such that $\forall n$, the running time is bounded by $cn^d$
• an algorithm is said to be efficient if it has a polynomial running time

Upper and Lower Bounds

• Asymptotic Upper Bound: a function $f(n)$ is $O(g(n))$ if there exists constants $c > 0, n_0 \geq 0$ s.t. $\forall n \geq n_0, \quad f(n) \leq cg(n)$
  • e.g. $100n \log_2n$ is $O(n^2)$ for $c = 100, n_0 = 1$
• Asymptotic Lower Bound: a function $f(n)$ is $\Omega(g(n))$ if there exist constants $c > 0, n_0 \geq 0$ s.t. $\forall n \geq n_0, \quad f(n) \geq cg(n)$
  • e.g. $\frac{n}{10}\log_2 n$ is $\Omega(n)$ for $c = 1, n_0 = 1024$

In general, we attempt to find a sufficiently large $n_0$ such that our upper and lower bounds are satisfied.

• Asymptotic Tight Bound: a function $f(n)$ is $\Theta(g(n))$ if $f(n)$ is $O(g(n))$ and $f(n)$ is $\Omega(g(n))$

Transitively:

• if $f = O(g)$ and $g = O(h)$, then $f = O(h)$
• if $f = \Omega(g)$ and $g = \Omega(h)$, then $f = \Omega(h)$
• if $f = \Theta(g)$ and $g = \Theta(h)$, then $f = \Theta(h)$

Additively:

• if $f = O(h)$ and $g = O(h)$, then $f + g = O(h)$
• Similar statements hold for lower and tight bounds
• if $k$ is a constant and there are $k$ functions: $f_i = O(h), 1\leq i \leq k$

• if $f = O(g)$, then $f + g = \Theta(g)$

Examples

$p,q,n > 0$

• $\forall \text{ constant } x > 0, \log n = O(n^x)$ e.g. $\log n = n^{0.00001}$
• $\forall \text{ constant } r > 1, d >0, n^d = O(r^n)$ e.g. $n^3 = O(1.1^n)$

03 - Review of Graphs and Priority Queues

Priority Queues: Motivation

Sorting

• Instance: Nonempty list $[x_1, x_2, \mathellipsis, x_n]$ of integers
• Solution: A permutation $[y_1, y_2, \mathellipsis, y_n]$ of $x_1, x_2, \mathellipsis, x_n$ such that $y_i \leq y_{i+1}$ for all $1 \leq i < n$$

Possible algorithm:

• insert each number into some data structure $D$
• Repeatedly find the smallest number in $D$, output it, and remove it
• To get $O(n \log n)$ running time, each "find minimum" step and each remove step must additively take $O(\log n)$

Priority Queues

• Store a set $S$ of elements where each element $v$ has a priority value $key(v)$
• smaller key values = higher priorities
• Supported operations:
  • find element with smallest key
  • remove smallest element
  • insert an element
  • delete an element
  • update the key of an element
• element deletion and key update require knowledge of the position of the element in the priority
• combines benefits of both lists and sorted arrays
• balanced binary tree
• heap order. For every element $v$ at a node $i$, the element $w$ at $i$'s parent satisfies $key(w) \leq key(v)$
• Each node's key is at least as large as its parent's
• storing nodes of the heap in an array:
  • Node at index $i$ has children at indices $2i$ and $2i+1$, with a parent at index $\lfloor \frac{i}{2} \rfloor$
  • index 1 is the root
  • if $2i > n$, where $n$ is the current number of elements in the heap, the node at index $i$ is a leaf

Inserting an Element: Heapify-up

• insert a new element at index $n+1$
• Fix heap order using Heapify-up(H, n+1)

Proof of Running Time Complexity for Heapify-up(i)

• each invocation decreases the second argument by a factor of at least 2
• after $k$ invocations, argument is at most $\frac{i}{2^k}$
• Therefore $\frac{i}{2^k} \geq 1$ which implies that $k \leq \log_2 i$ therefore heapify up is $O(\log i)$

Deleting an Element: Heapify-down

• Suppose $H$ has $n+1$ elements
• Delete element $H[i]$ moving element at $H[n+1]$ to $H[i]$
• If element at $H[i]$ is too small, fix the heap order using Heapify-up(H, i)
• If element at $H[i]$ is too large, fix heap order using Heapify-down(H, i)

Proof of Running Time Complexity for Heapify-down(i)

• Each invocation increases is second argument by a factor of at least 2
• after $k$ invocations arguments must be at least $i2^k \leq n$, which implies that $k \leq \log_2 \frac{n}{i}$
• Therefore running time is $O(\log_2 \frac{n}{i})$

Sorting

• Instance: Nonempty list $[x_1, x_2, \mathellipsis, x_n]$ of integers
• Solution: A permutation $[y_1, y_2, \mathellipsis, y_n]$ of $x_1, x_2, \mathellipsis, x_n$ such that $y_i \leq y_{i+1}$ for all $1 \leq i < n$$

Final algorithm:

• Insert each number in a priority queue $H$
• Repeatedly find the smallest number in $H$, output it, and delete it from $H$

Thus, each insertion and deletion take $O(\log n)$ for a total running time of $O(n \log n)$

Graphs: Motivation

• Contact tracing hahaaaaa

Taxonomy of a Graph

• comprised of vertices and (directed / undirected) edges, they can form face.

• Euler Path: Only possible if the number of nodes with odd degree is at most 2

• Formally, an Undirected graph $G = (V, E)$ where $V, E$ are sets of vertices and edges with $E \subseteq V \times V$

  • Elements of $E$ are unordered pairs
  • $Edge(u, v)$ is incident on $u,v$ meaning $u,v$ are neighbors of one another
  • Exactly one edge between any pair of nodes
  • $G$ contains no self loops, i.e. no edges of the from $(u,u)$

• Formally, an directed graph $G = (V, E)$ where $V, E$ are sets of vertices and edges with $E \subseteq V \times V$

  • Elements of $E$ are ordered pairs
  • $e = (u, v)$ where $u$ is the tail of the edge $e$, $v$ is the head, and we can say that $e$ is directed from $u$ to $v$
  • A pair of nodes may be connected by two directed edges $(u,v)$ and $(v,u)$
  • $G$ contains no self loops

• A $v_1 - v_k$ path in an undirected graph $G = (V,E)$ is a sequence of $P$ nodes $v_1, v_2, \mathellipsis, v_{k-1}, v_k; v_k \in V$ s.t. every consecutive pair of nodes $v_i; v_{i+1}, 1 \leq i < k$ is connected by an edge $E$

• a path is simple if all its nodes are distinct

• a cycle is a path where $k>2$, the first $k-1$ nodes are distinct and $v_1 = v_k$

• An undirected graph $G$ is connected if, for every pair of nodes $u,v \in V$, there is a path from $u$ to $v$ in $G$

• The distance $d(u,v)$ between nodes $u,v$ is the minimum number of edges in any $u-v$ path

• The connected component of $G$ containing $s$ is the set of all nodes $u$ such that there is an $s-u$ path in $G$

Computing Connected Components

• Rather than computing the connected component of $G$ that contains $s$ and check if $t$ is in that component, we can "explore" $G$ starting from $s$, maintaining a set $R$ of visited nodes

Breadth First Search

• Explore $G$ starting at $s$ and going "outward" in all directions, adding nodes one "layer" at a time
• Layer $L_0$ only contains $s$
• Layer $L_1$ contains $s$ and all its neighbors, etc. etc.
• Layer $L_0, L_1, \mathellipsis , L_j, L_{j+1}$ contains all nodes that:
  • do not belong to an earlier layer
  • are connected by an edge to a node in layer $L_j$
  • The shortest path from $s$ to each node contains $j$ edges
• Claim: For each $j \geq 1$, layer $L_j$ consists of all nodes exactly at distance $j$ from $S$
• A non-tree edge is an edge of $G$ that does not belong to the BFS tree $T$

Proof

• There is a path from $s$ to $t$ if an only iff $t$ is a member of some layer
• Let $v$ be a node in layer $L_{j+1}$ and $$u$be the "first" node in$L_j$such that$(u,v)$is an edge in$G$. Consider the graph$T$formed by all edges, directed from$u$to$v$
  • Notice that $T$ is a tree because it is connected and the number of edges in $T$ is the number of nodes in all the laters minus one
  • $T$ is called the BFS Tree

Inductive Proof of BFS Distance Property

• for every $j \geq 0$, for every node $u \in L_j$, $d(s, u) = j$
• Basis: $k =0$, $d(s,s) = 0$
• Inductive Hypothesis: Assume the claim is true for every node $v \in L_k$, $d(s, v) = k$
• Inductive Step: Prove for every node $x \in L_{k+1}$, $d(s, x) = k + 1$
  • $d(s,x) = d(s, y) + 1$ if $y$ is a node in $L_k$
  • Therefore $d(s,x) = k+1$

Depth First Search

• Explore $G$ as if it were a maze: start from $s$, traverse first edge out (to node $v$), traverse first edge out of $v$, . . . , reach a dead-end, backtrack, repeat

Properties of each

• BFS and DFS visit the same set of nodes, but in a different order

Representing Graphs

• A Graph $G = (V,E)$ has two input parameters: $|V| =n, |E| = m$, with $n-1 \leq m \leq \binom{n}{2}$
  • Size of graph is defined to be $m + n$
  • Strive for algorithms whose running time is linear in graph size i.e. $)(m + n)$
• We assume that $V = {1, 2, \mathellipsis, n}$
• Use an Adjaceny Matrix: $n \times n$ boolean matrix, where the entry in row $i$, col $j$ is 1 iff the graph contains the edge $(i, j)$
  • the space used is $\Theta(n^2)$, which is optimal in the worst case
  • can check if there is an edge between nodes $i$, $j$ in $O(1)$ time
  • iterate over all the edges incident on node $i$ in $\Theta(n)$ time
• Use an Adjaceny List: array $Adj$, where $Adj[v]$ stores the list of all nodes adjacent to $v$
  • an edge $e = (u,v)$ appears twice: $Adj[u],$Adj[v]$
  • $n_v$ is the number of neighbors of node $v$
  • space used is $O(\displaystyle\sum_{v \in G}n_v) = O(m+n)$
  • check if there is an adge between nodes $u, v$ in $O(n_u)$ time
  • Iterate over all the edges incident on node $u$ in $\Theta(n_u)$ time
  • Inserting an edge takes $O(1)$ time
  • Deleting an edge takes $O(n)$ time

04 - Linear-Time Graph Algorithms

Bipartite Graphs

• A graph $G = (V, E)$ is bipartite if $V$ can be partitioned into two subsets $X,Y$ such that every edge in $E$ has one endpoint in $X$ and one in $Y$

  • $X \times X \cap E = \emptyset$ and $Y \times Y \cap E = \emptyset$
  • Color the nodes in $X$ red and the nodes in $Y$ blue. No edge in $E$ connects nodes of the same graph

• no cycle with an odd number of nodes is bipartite, similarly all cycles of even length are bipartite

• Therefore, if a graph is bipartite, then it cannot contain a cycle of odd length

Algorithm for Testing Bipartite

• Assume $G$ is connected, otherwise apply the algorithm to each connected component separately
• Pick an arbitrary node $s$ and color it red.
• Color all it's neighbors blue. Color the uncolored neighbors of these nodes red, and so on till all nodes are colored
• Check if every edge has endpoints of different colours

more formally:

1. Run BFS on $G$. Maintain an array for the color
2. When we add a node $v$ to a layer $i$, set $\text{color[i]}$ to red if $i$ is even, blue of odd
3. At the end of BFS, scan all the edges to check if there is any edge both of whose endpoints received the same color

Running time is linear proportional to the size of the graph: $O(m + n)$ since we do a constant amount of work per node in addition to the time spent by BFS.

Proof of Correctness of a "two-colorable" algorithm

Need to prove that if the algorithm says $G$ is bipartite, then it is actually bipartite AND need to prove that if $G$ is not bipartite, can we determine why?

• Let $G$ be a graph and let $L_0, L_1, \mathellipsis, L_k$ be the layers produced by the BFS, starting at node $s$. Then exactly one of the following statements is true:
  • No edge of $G$ joins two nodes in the same layer: Bipartite since nodes in the even laters can be colored red and those in odd blue
  • There is an edge of $G$ that joins two nodes in the same layer: Not Bipartite
  • $| L_i - L_j | = 1, \quad \forall L \in BFS$

05 - Greedy Algorithms

• Greedy algorithms: make the best current choice without looking back. Assume the choices made prior were perfect

Example Problem: Interval Scheduling

• At an amusement park, want to compute the largest number of rides you can be on in one day

• Input: start and end time of each ride

• Constraint: cannot be in two places at one time

• Instance: nonempty set $\{(s(i), f(i)), 1 \leq i \leq n\}$ of start and finish times of $n$ jobs

• Solution: The largest subset of mutually compatible jobs

• Two jobs are compatible if they do not overlap

• Problem models the situation where you have a resource, a set of fixed jobs, and you want to schedule as many jobs as possible

• For any input set of jobs, the algorithm must provably compute the largest set of compatible jobs (measured by interval count, not cumulative interval length)

Template for a Greedy Algorithm

• Process jobs in some order. Add next job to the result if it is compatible with the jobs already in the result
• key question: in what order should we process job?
  • earliest start time: increasing order of start time $s(i)$
  • earliest finish time: increasing order of start time $f(i)$
  • shortest interval: increasing order of $f(i) - s(i)$
  • fewest conflicts: increasing order of the number of conflicting jobs

Earliest Finish Time

• the most optimal general solution

Proof of Optimality

• Claim $|A|$ is a compatible set of jobs that is the largest possible in any set of mutually compatible jobs
• Proof by contradiction that there's no "better" solution at each step of the algorithm
  • need to define "better", and what a step is in terms of the progress of the algorithm
  • order the output in terms of increasing finish time for a measure of progress
• Finishing time of a job $r$ selected by $A$ must be less than or equal to the finishing time of a job $r$ selected by any other algorithm
• Let $O$ be an optimal set of jobs. We will show that $|A| = |O|$
• Let $i_1, i_2, \mathellipsis, i_k$ be the set of jobs in $A$ in order of finishing time
• Let $j_1, j_2, \mathellipsis, j_m$ be the set of jobs in $O$ in order of $m \geq k$
• Claim: for all indices $r \leq k, \quad f(i_r) \leq f(j_r)$
• Base case: is it possible for finish time of the first job of our algorithm to be later than the opposing job?
  • $f(i_1) > f(j_1)$ is not possible, only $f(i_1) \leq f(j_1)$
• Inductive Hypothesis: this is always the case for any generic job index $r$:
  • $f(i_r) \leq f(j_r)$ for some $r \leq k$
• Inductive Step: show that the same claim holds for the next job:
  • $f(i_{r+1}) \leq f(j_{r+1})$ for some $r+1 \leq k$
  • $s(j_{r+1}) \geq f(i_r) \geq f(i_r)$
• claim $m = k$: $f(i_{k}) \leq f(j_{k}) \leq s(j_{k+1})$

A complete proof can be found here:

Implementing EFT

• Sort jobs in order of increasing finish time
• Store starting time of jobs in an array $S$
• $k=1$
• While $k \leq |S|$
  • output job $k$
  • Let the finish time of job $k$ be $f$
  • Iterate over $S$ from $k$ onwards to find the first index $i$ s.t. $S[i] \geq f$
  • $k = i$
• Must be careful to iterate over $S$ s.t. we never scan same index more than once
• Running time is $O(n \log n)$ since it's dominated by the first sorting step

Scheduling to Minimize Lateness

• Suppose a job $i$ has a length $t(i)$ and a deadline $d(i)$
• want to schedule all $n$ jobs on one resource
• Goal is to assign a starting time $s(i)$ to each job such that each job is delayed as little as possible
• A job $i$ is delayed if $f(i) > d(i)$; the lateness of job is $\max(0, f(i) - d(i))$
• the lateness of a schedule is $\max \limits_{1 \leq i \leq n}(\max(0, f(i) - d(i)))$
  • the largest of each job's lateness values

Minimizing Lateness

• Instance: Set $\{ (t(i), d(i)), 1 \leq i \leq n \}$ of lengths of deadlines of $n$ jobs
• Solution: Set $\{ s(i), 1 \leq i \leq n \}$ such that $\max \limits_{1 \leq i \leq n}(\max(0, f(i) - d(i)))$ is as small as possible

Template for Greedy Algorithm

• Key question: In what order should we schedule the jobs:

  • Shortest length: increasing order of length $t(i)$. Ignores deadlines completely, shortest job may have a very late deadline:

  $i$	1	2
  $t(i)$	1	10
  $d(i)$	100	10

  • Shortest slack time: Increasing order of $d(i) - t(i)$. Bad for long jobs with late deadlines. Job with smallest slack may take a long time:

  $i$	1	2
  $t(i)$	1	10
  $d(i)$	2	10

  • Earliest Deadline: Increasing order deadline $d(i)$. Correct? Does it make sense to tackle jobs with earliest deadlines first?

Proof of Earliest Deadline Optimality

Inversions

• A schedule has an inversion if a job $i$ with a deadline $d(i)$ is scheduled before another job $j$ with an earlier deadline $d(j)$ i.e. $d(j) < d(i), s(i) < s(j)$
  • if two jobs have the same deadline, they cannot cause an inversion
• in $n$ jobs, the maximum amount of inversion is $n \choose 2$
• Claim: if a schedule has and inversion, then there must be a pair of jobs $i, j$ such that $j$ is scheduled immediately after $i$ and $d(j) < d(i)$

Proof of Local Inversion

• If we have an inversion between $l, m$ s.t. $s(l) < s(m), d(l) > d(m)$, then we can find some inverted $i,j$ scheduled between $l,m$
• This is because: in a list where each element is greater than the last (in terms of deadline), then the list is sorted.
• The contrapositive of this is: if a list is unsorted, then there are two adjacent elements that are unsorted.

Properties of Schedules

• Claim 1: The algorithm produces a schedule with no inversion and no idle time (i.e. jobs are tightly packed)
• Claim 2: All schedules (produced from the same input) with no inversions have the same lateness
  • Case 1: All jobs have distinct deadlines. There is a unique schedule with no inversions and no idle time.
  • Case 2: Some jobs have the same deadline. Ordering of the jobs does not change the maximum lateness of these jobs.
• Claim 3: There is an optimal schedule with no idle time.
• Claim 4: There is an optimal schedule with no inversions and no idle time.
  • Start with an optimal schedule $O$ (that may have inversions) and use an exchange argument to convert $O$ into a schedule that satisfies Claim 4 and has lateness not larger than $O$.
  • If $O$ has an inversion, let $i, j$ be consecutive inverted jobs in $O$. After swapping $i, j$ we get a schedule $O'$ with one less inversion.
  • Claim: The lateness of $O'$ is no larger than the lateness of $O$
  • It is sufficient to prove the last item, since after $n \choose 2$ swaps, we obtain a schedule with no inversions whose lateness is no larger than that of $O$
  • In $O$, assume each job $r$ is scheduled for the interval $[s(r), f(r)]$ and has lateness $\mathcal l(r)$. For $O'$, let the lateness of $r$ be $l'(r)$
    • Claim: $l'(k) = l(k), \quad \forall k \neq i,j$
    • Claim: $l'(j) = l(j)$,
    • Claim: $l'(j) \leq l(j)$ because $l'(j) = f(j) - d_i \leq f(j) - d_j = l(j)$
  • N.B. common mistakes with exchange arguments:
    • Wrong: start with algorithm's schedule A and argue it cannot be improved by swapping two jobs
    • Correct: Start with an arbitrary schedule O (which can be optimal) and argue that O can be converted into a schedule that is essentially the same as A without increasing lateness
    • Wrong: Swap two jobs that are not neighboring in $O$. Pitfall is that the completion time of all intervening jobs then changes
    • Correct: Show that an inversion exists between two neighboring jobs and swap them
• Claim 5: The greedy algorithm produces an optimal schedule, follows from 1, 2, 4

Summary

• Greedy algorithms make local decisions
• Three strategies:
  • Greedy algorithm stays ahead - Show that after each step in the greedy algorithm, its solution is at least as good as that produced by any other algorithm
  • Structural bound - First, discover a property that must be satisfied by every possible solution. Then show that the (greedy) algorithm produces a solution with this property
  • Exchange argument - Transform the optimal solution in steps into the solution by the greedy algorithm without worsening the quality of the optimal solution

06 - Greedy Graph Algorithms

The Shortest Path Problem

• $G(V,E)$ is a connected, directed graph. Each edge has a length $l(e) \geq 0$
• length of a path $P$ us the sum of the lengths of the edges in $P$
• Goal: compute the shortest path from a specified start node $s$ to every other node in the graph
• Instace: A directed graph $G(V,E)$, a function $I: E \rightarrow \reals^+$ and a node $s \in V$
• Solution: A set $\{P_u, u \in V\}$ of paths, where $P_u$ is the shortest path in $G$ from $s$ to $u$

Generalizing BFS

• If all edges have the same wight, or distance, BFS would work, processing nodes in order of distance.
• What if the graph has integer edge weights, can we make the graph unweighted?
  • yes, placing dummy edges and nodes to pad out lengths > 1 at the expense of memory and running time
  • Edge weight of $w$ gets $w - 1$ nodes
  • Size of the graph (and therefore runtime) becomes $m + n + \sum_{e \in E} l(e)$. Pseudo-polynomial time depending on input values

Dijkstra's Algorithm

• Famous for pointing out the harm of the goto command, in doing so developed the shortest path algorithm
• Like BFS: explore nodes in non-increasing order of distance $s$. Once a node is explored, its distance is fixed
• Unlike BFS: Layers are not uniform, edges are explored by evaluating candidates by edge wight
• For each unexplored node, determine "best" preceding explored node. Record shortest path length only through explored nodes
• Like BFS: Record previous node in path, and build a tree.

Formally:

• Maintain a set $S$ of explored nodes
  • For each node $u \in S$, compute $d(u)$, which (we will prove, invariant) is the length of the shortest path from $s$ to $u$
  • For each node $x \notin S$, maintain a value $d'(x)$, which is the length of the shortest path from $s$ to $x$ using only the nodes in $S$ and $x$ itself
• Greedily add a node $v$ to $S$ that has the smallest value of $d'(v)$