Directed graph G = ( V , E )

•Transitive closure ( connected cmp for undirected G )

•A =( aij )n×n

        aij = 1 ,  i → j  ,  ( i , j ) 屬於 E

•A2= B = ( bij )

        bij = ai1•a1j + ai2•a2j +••+ ain•anj

            = 1 ,   i → k → j

•A3=B•A = ( cij )                                 

        cij = bi1•a1j + bi2•a2j +••+ bin•anj

            = 1 , i → k → l → j

•A* = A + A2 +•••+ An-1 + An +•••

         = A + A2 +•••+ An-1

    G* = ( V , E*) a*ij=1 , i~~~~~→j

�n　

　

•shortest path ( all pairs )

•A = ( aij ) n×n

        aij = dist( i , j )

•A2 = ( bij )

        bij = ( ai1 + a1j )min( ai2 + a2j )min•••min( ain + anj)

                     = shortest distance i → k → j

•A3 = ( cij ) = shortest distance i → k → i → j

•A* = ( a*ij ) = shortest distance i ~~~~~→j

　

T = o ( N4 )

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