In [1]:
%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()

# 25 All-Pairs Shortest Paths¶

### 25.1 Shortest paths and matrix multiplication¶

This section presents a dynamic-programming algorithm:

1. Characterize the structure of an optimal solution. all subpaths of a shortest path are shortest paths.

2. Recursively define the value of an optimal solution. let $l_{i, j}^{(m)}$ be the minimum weight of any path from vertex $i$ to vertex $j$ that contains at most $m$ edges. Thus,

l_{i, j}^{(0)} = \begin{cases}
0 & \quad \text{if } i = j \\
\end{cases}

we recursively define:

l_{i, j}^{(m)} = \displaystyle \min_{1 \leq k \leq n} \{ l_{i, k}^{(m-1)} + w_{k, j} \}

3. Compute the value of an optimal solution in a bottom-up fashion. We now compupte a series of matrices $L^{(1)}, L^{(2)}, \dotsc, L^{(n-1)}$, where $L^{(1)} = W$.

In [3]:
Out[3]:
<matplotlib.image.AxesImage at 0x116f44ef0>

If we replace $\infty$ by 0 in EXTEND-SHORTEST-PATHS, it can be converted to matrix muplication: $L^{(n-1)} = W^{n-1}$.

In [ ]:
#Exercises