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 = ai1a1j + ai2a2j +••+ ainanj

            = 1 ,   i k j

A3=BA = ( cij )                                 

        cij = bi1a1j + bi2a2j +••+ binanj

            = 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³ )