In [1]:
# %load ../../preconfig.py
%matplotlib inline
import matplotlib.pyplot as plt
import seaborn as sns
sns.set(color_codes=True)
plt.rcParams['axes.grid'] = False
#import numpy as np
#import pandas as pd
#import sklearn
#import itertools
import logging
logger = logging.getLogger()
In a shortest-paths problem,
Given: a weighted, directed graph $G = (V, E)$, with weight function $w : E \to \mathcal{R}$.
path $p = < v_0, v_1, \dotsc, v_k >$, so
$$w(p) = \displaystyle \sum_{i=1}^k w(v_{i-1}, v_i)$$.
we define the shortest-path weight $\delta(u, v)$ from $u$ to $v$ by \begin{equation} \delta(u, v) = \begin{cases} \min{ w(p) : u \overset{p}{\to} v } & \text{if $p$ exist}\\ \infty & \text{otherwise} \end{cases} \end{equation}
variants:
Optimal substructure of a shortest path:
subpath of $p$ is a shortest path between two of its internal nodes if $p$ is a shortest path.
Negative-weight edges: whether a negative weight cycle exists?
Cycles:
Representing shortest paths:
a "shortest-paths tree": a rooted tree containing a shortest path from the source $s$ to every vertex that is reachable from $s$.
Relaxation:
modify the node's upper bound if detect a shorter path.
INITIALIZE-SINGLE-SOURCE(G, s)
for each vertex v in G.V
v.d = infty
v.pi = NIL
s.d = 0
RELAX(u, v, w)
if v.d > u.d + w(u, v)
v.d = u.d + w(u, v)
v.pi = uProperties of shortest paths and relaxtion
it returns a boolean valued indicating whether or not there is a negative-weight cycle that is reachable from the source.
The algorithm relaxes edges, progressively decreasing an estimate $v.d$ on the weight of a shortest path from the source $s$ to each vertex $v \in V$ until it achieves the actual shortest-path weight $\delta(s, v)$.
The Bellman-Fold algorithm runs in time $O(VE)$.
In [2]:
plt.imshow(plt.imread('./res/bellman_ford.png'))
Out[2]:
In [3]:
plt.imshow(plt.imread('./res/fig24_4.png'))
Out[3]:
In [4]:
plt.imshow(plt.imread('./res/dag.png'))
Out[4]:
In [5]:
plt.imshow(plt.imread('./res/fig24_5.png'))
Out[5]:
interesting application: to determine critical paths in PERT chart analysis.
weighted, directed graph $G = (V, E)$ and all $w(u, v) \geq 0$.
Dijkstra's algorithm maintains a set $S$ of vertices whose final shortest-path weights from the source $s$ have already been determined.
we use a min-priority queue $Q$ of vertices, keyed by their $d$ values.
In [6]:
plt.imshow(plt.imread('./res/dijkstra.png'))
Out[6]:
In [7]:
plt.imshow(plt.imread('./res/fig24_6.png'))
Out[7]:
In [8]:
plt.imshow(plt.imread('./res/inequ.png'))
Out[8]:
In [9]:
plt.imshow(plt.imread('./res/fig24_8.png'))
Out[9]:
In [ ]: