플로이드-와샬 알고리즘

Floyd-Warshall Algorithm

전체쌍(All-pair) 최단경로 알고리즘

의사 코드

Shortest(A, C)
{
  for(i=1; i<=n; i++)
    do for(j=1; j<=n; j++)
      do A[i,j] = C[i,j];
        P[i,j] = 0;
      for(i=1; i<=n; i++)
        do A[i,i] = 0;
  for(k=1; k<=n; k++)
    do for(i=1; i<=n; i++)
      do for(j=1; j<=n; j++)
        if A[i,j] > A[i,k] + A[k,j]
           A[i,j] = A[i,k] + A[k,j]
           P[i,j] = k;
}