Directed graph G = ( V , E )
¡E
Transitive closure ( connected cmp for undirected G )¡EA =( aij )n¡Ñn
aij = 1 , i ¡÷ j , ( i , j ) ÄÝ©ó E
¡EA2= B = ( bij )
bij = ai1¡Ea1j + ai2¡Ea2j +¡E¡E+ ain¡Eanj
= 1 , i ¡÷ k ¡÷ j
¡EA3=B¡EA = ( cij )
cij = bi1¡Ea1j + bi2¡Ea2j +¡E¡E+ bin¡Eanj
= 1 , i ¡÷ k ¡÷ l ¡÷ j
¡EA* = A + A2 +¡E¡E¡E+ An-1 + An +¡E¡E¡E
= A + A2 +¡E¡E¡E+ An-1
G* = ( V , E*) a*ij=1 , i~~~~~¡÷j
ƒn¡@
¡@ ¡Eshortest path ( all pairs ) ¡EA = ( aij ) n¡Ñnaij = dist( i , j )
¡EA2 = ( bij )bij = ( ai1 + a1j )min( ai2 + a2j )min
¡E¡E¡Emin( ain + anj)= shortest distance i
¡÷ k ¡÷ j¡E
A3 = ( cij ) = shortest distance i ¡÷ k ¡÷ i ¡÷ j¡E
A* = ( a*ij ) = shortest distance i ~~~~~¡÷j ¡@T = o ( N4 )
if apply Digkstra's algorithm N times ¡÷ T=O( N³ )
¡@