Directed graph G = ( V , E )

¡ETransitive 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¡Ñn

        aij = dist( i , j )

¡EA2 = ( bij )

        bij = ( ai1 + a1j )min( ai2 + a2j )min¡E¡E¡Emin( ain + anj)

                     = shortest distance i ¡÷ k ¡÷ j

¡EA3 = ( cij ) = shortest distance i ¡÷ k ¡÷ i ¡÷ j

¡EA* = ( a*ij ) = shortest distance i ~~~~~¡÷j

¡@

T = o ( N4 )

if apply Digkstra's algorithm N times ¡÷ T=O( N³ )

¡@