플로이드-워셜 알고리즘

Floyd-Warshall 알고리즘은 모든 쌍의 최단 경로를 찾는 데 사용됩니다. 이 알고리즘은 주어진 에지 그래프에서 모든 정점 쌍 사이의 최단 경로를 찾는 데 사용됩니다.

G = (V,E)를 n개의 꼭짓점이 있는 유향 그래프라고 합니다. cost를 cost(i,i) = 0, 1<=i<=n이 되도록 G에 대한 비용 인접 행렬이라고 합니다.

비용(i,j) = 간선의 길이 또는 비용 (i,j), if(i,j) ∈ E(G) 및 비용(i,j)= ∞ if (i,j) ∉ E(G)

모든 쌍 최단 경로 문제는 A(i,j)가 i에서 j까지의 최단 경로 길이가 되도록 행렬 A를 결정하는 것입니다.

k가 i에서 j 경로 사이의 가장 높은 중간 정점이라고 하면 i에서 k 경로는 k-1보다 큰 지수를 가진 정점을 통과하지 않는 그래프 G의 최단 경로입니다. 유사하게 k에서 j까지의 경로는 그래프 G에서 k-1보다 큰 인덱스를 갖는 정점을 통과하지 않는 최단 경로입니다.

먼저 가장 높은 중간 정점 k를 찾은 다음 i에서 k로, k에서 j로 가는 두 개의 최단 경로를 찾아야 합니다.

그런 다음 A^k(i,j)를 사용하여 i에서 j까지 k보다 큰 인덱스 정점을 통과하지 않는 최단 경로의 길이를 나타냅니다.

A^0(i,j)=비용(i,j)

가장 높은 중간 정점 k를 통과하면

A^k(i,j) = A^k-1(i,k)+A^k-1(k,j)

그렇지 않은 경우 가장 높은 중간 정점은

A^k(i,j) = A^k-1(i,j)

$A^{k}$(i,j)에 대한 반복을 얻으려면 둘 다 결합해야 합니다.

A^k(i,j) =min{ A^k-1(i,j), A^k-1(i,k)+A^k-1(k,j)}, 여기서 k>=1



참고: 선택한 중간 정점의 경우 해당 정점에 속하는 경로는 동일하게 유지됩니다.



위의 행렬을 취함으로써 우리는 $A^{1}$ 행렬을 얻을 수 있습니다.

A^1(2,3) = 분{A^0(2,3),A^0(2,1)+A^0(1,3)}

$A^{1}$(2,3) = 최소{2,8+∞} = 2

A^1(2,4) = 분{A^0(2,4),A^0(2,1)+A^0(1,4)}

A^1(2,4) = 최소{∞,8+7} = 15

A^1(3,2) = 분{A^0(3,2),A^0(3,1)+A^0(1,2)}

A^1(3,2) = 최소{∞,5+3} = 8

A^1(3,4) = 분{A^0(4,3),A^0(3,1)+A^0(1,4)}

A^1(3,4) = 최소{1,5+7} = 1

A^1(4,2) = 분{A^0(4,2),A^0(4,1)+A^0(1,2)}

$A^{1}$(4,2) = 최소{∞,2+3} = 2

A^1(4,3) = 분{A^0(4,3),A^0(4,1)+A^0(1,3)}

A^1(4,3) = 최소{∞,2+∞} = 2

비슷하게;

연산

for(k=1;k<=n;k++)
{
  for(i=1;i<=n;i++)
  {
    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];
      }
    }
  }
}

프로그램

#include<stdio.h>
void floyd(int a[4][4], int n)
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(a[i][j]>a[i][k]+a[k][j])
                {
                    a[i][j]=a[i][k]+a[k][j];
                }
            }
        }
    }
    printf("All Pairs Shortest Path is :\n");
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                printf("%d ",a[i][j]);
            }
            printf("\n");
        }
}
int main()
{
    int cost[4][4] = {{0, 3, 999, 4}, {8, 0, 2, 999}, {5, 999, 0, 1}, {2, 999, 999, 0}}; 
    int n = 4;

    floyd(cost,n);
}

산출

꼭지점을 입력하지 마십시오:4
인접 행렬의 비용은 다음과 같습니다.
0 3 9999 7
8 0 2 9999
5 9999 0 1
2 9999 9999 0
모든 쌍의 최단 경로는 다음과 같습니다.
0 3 5 6
5 0 2 3
3 6 0 1
2 5 7 0