1.  Shur complement

The Shur complement method is an asymptotically better way to calculate the all points shortest path matrix.

1. Partition the graph into 2 sets of nodes {S,T}

There will be 4 kinds of edges:

From/To	T	S
T	A	B
S	C	D

= M As an example, B contains all edges from T to S

1. compute A^* (all internal connections in T)
2. F = D+CA^*B
3. F^*

Form the matrix:

M^* = (

A*+A*BF*CA*	A*BF*
F*CA*	F*

)

This matrix is the all shortest path matrix.

Proof: Consider each possible path in terms of combinations of A,B,C,D and think about which entries these will include.

(CA^*B)_ij = shortest path form i to j using only vertices in T.

1.1  Timing analyses

T(n) = 2T(ⁿ/₂)+cn³ = cn³+2c(ⁿ/₂)³+... = O(n³) This is better than the all points shortest path calculated by rings method.