Notes - DAA HT23, Shortest paths and relaxation
Shortest paths and relaxation
What is the process of relaxing an edge $(u, v)$?
Updating the distance to $v$ if going via $u$ is cheaper.
Let $\delta(x, y)$ represent the shortest path distance between $x$ and $y$ and let $w(u, v)$ represent the weight of the edge $(u, v)$. What is the triangle inequality in the context of shortest paths from $s$?
For any edge $(u, v) \in E$
\[\delta(s, v) \le \delta(s, u) + w(u, v)\]Let $\delta(x, y)$ represent the shortest path distance between $x$ and $y$. What is the upper-bound property in the context of shortest paths from $s$?
For every vertex $v$ we have
\[v.d \ge \delta(s, v)\]and once it is equal, it never changes.
Still need to do:
- Convergence property
- Path-relaxation property
- Predeccessor-subgraph property
Dijkstra’s Algorithm
Breadth-first search and Dijkstra’s algorithm are almost the same algorithm but with one small change. What data structure does Dijkstra’s use rather than a FIFO queue?
A min-priority queue.
What is the running time of Dijkstra’s algorithm?
Can you state pseudocode for Dijkstra’s algorithm on a graph $G$ and starting from $s$?
DIJKSTRA(G, s):
for every vertex v in G:
v.pi = null
v.d = infinity
s.d = 0
Q = priority queue indexed by distance
while Q is nonempty:
u = DEQUEUE(Q)
for every vertex v adjacent to u:
if u.d + w(u, v) < v.d:
v.d = u.d + w(u, v)
v.pi = u
DECREASE-KEY(Q, v, v.d)
Bellman-Ford algorithm
Dijkstra’s algorithm doesn’t work when there’s negative weights. Assuming the graph has no negative cycles, what’s the name of the algorithm that solves the shortest path problem for graphs with negative weights?
Bellman-Ford
What’s the time complexity of the Bellman-Ford algorithm?
How many times does the Bellman-Ford algorithm relax every edge?
$ \vert V \vert -1$ times.
Can you state pseudocode for the Bellman-Ford algorithm on a graph $G$ starting from $s$?
BELLMAN-FORD(G, s):
for every vertex v in G:
v.d = infinity
v.pi = null
s.d = 0
for i in 1 to |V| - 1:
for (u, v) in E:
if u.d + w(u, v) < v.d:
v.d = u.d + w(u, v)
v.pi = u
for each (u, v) in E:
if u.d + w(u, v) < v.d:
return false
return true
Shortest paths in DAGs
When the input graph is a DAG (possibly with negative weights), there’s better algorithms than Dijkstra’s or the Bellman-Ford algorithm for finding shortest paths. What’s the best time complexity you can achieve?
Can you state pseudocode for finding the shortest path in a DAG $G$ and from a start vertex $s$?
DAG-SHORTEST-PATHS(G, s):
topologically sort vertices of G
for each vertex v in G:
v.d = infinity
v.pi = null
s.d = 0
for each vertex u in the topologically sorted G:
for each vertex v adjacent to u
if u.d + w(u, v) < v.d:
v.d = u.d + w(u, v)
v.pi = u
Can you briefly justify why
DAG-SHORTEST-PATHS(G, s):
topologically sort vertices of G
for each vertex v in G:
v.d = infinity
v.pi = null
s.d = 0
for each vertex u in the topologically sorted G:
for each vertex v adjacent to u
if u.d + w(u, v) < v.d:
v.d = u.d + w(u, v)
v.pi = u
is a correct algorithm?
DAG-SHORTEST-PATHS(G, s):
topologically sort vertices of G
for each vertex v in G:
v.d = infinity
v.pi = null
s.d = 0
for each vertex u in the topologically sorted G:
for each vertex v adjacent to u
if u.d + w(u, v) < v.d:
v.d = u.d + w(u, v)
v.pi = u
By considering vertices in topological order, a vertex is only considered once all of its predecessors have been processed.
Floyd-Warshall algorithm
What’s the $O( \vert V \vert ^3)$ algorithm for finding the shortest-path between every two vertices in a graph called?
The Floyd-Warshall algorithm.
What’s the time complexity of the Floyd-Warshall algorithm?::
\[O(|V|^3)\]When solving the all-pairs shortest path problem using the Floyd-Warshall algorithm, what data structure do you use for keeping track of intermediate results (that are used by the dynamic programming algorithm)?
which is the shortest distance from $i$ to $j$ whose intermediate nodes are in the interval $[1, k]$.
What optimal substructure about $s \xrightarrow{p _ 1} u \xrightarrow{p _ 2} v$ is used by the Floyd-Warshall algorithm?
If $s \xrightarrow{p _ 1} u \xrightarrow{p _ 2} v$ is the shortest path from $s$ to $v$, then
- $s \xrightarrow{p _ 1} u$ is the shortest path from $s$ to $u$
- $u \xrightarrow{p _ 2} v$ is the shortest path from $u$ to $v$.
Let
\[d[i, j, k]\]
be the shortest distance from $i$ to $j$ whose intermediate nodes are in the interval $[1, k]$. Given also that if $s \xrightarrow{p _ 1} u \xrightarrow{p _ 2} v$ is the shortest path from $s$ to $v$, then
- $s \xrightarrow{p _ 1} u$ is the shortest path from $s$ to $u$
- $u \xrightarrow{p _ 2} v$ is the shortest path from $u$ to $v$.
then what recurrence can you use to solve the all-pairs shortest path algorithm?
Can you give pseudocode for the Floyd-Warshall all-pairs shortest path algorithm?
FLOYD-WARSHALL(G, w):
for i = 1 to |V|:
for j = 1 to |V|:
d[i, j, 0] = infinity
for each edge (i, j) in E:
d[i, j, 0] = w(i, j)
for k = 0 to |V| - 1
for i = 1 to |V|
for j = 1 to |V|
d[i, j, k+1] = min(
d[i, j, k],
d[i, k+1, k] + d[k+1, j, k]
)