Multi - Source SSP

\(D^k[i][j]\): The shortest distance from the node \(i\) to the node \(j\) cross the node \(l(l \leq k)\).

Updata \(D^k[i][j]\) from \(D^{k-1}[i][j]\) by evaluating:

\[D^k[i][j] = \min \left\{ D^{k-1}[i][j], D^{k-1}[i][k] + D^{k-1}[k][j] \right\}\]

Interface

class MGraph(num_vert)

__init__(num_vert) → None

connect(v: int, w: int, weight: int) → None

floyd() → list