한국어
한국어
그래프 이론에서 가장 짧은 경로 문제는 지시되지 않은 그래프 또는 방향이없는 그래프에서 두 정점 사이의 가장 짧은 경로를 찾는 것과 관련된 고전적인 알고리즘 문제입니다. Floyd-Warshall 알고리즘은이 문제를 해결하는 데 사용되는 전형적인 동적 프로그래밍 알고리즘입니다. 이 기사는 PHP를 사용하여 Floyd-Warshall 알고리즘을 구현하는 방법을 자세히 설명합니다.
Floyd-Warshall 알고리즘은 그래프의 모든 정점 사이의 가장 짧은 경로 길이를 반복하여 가장 짧은 경로 문제를 해결하는 알고리즘입니다. 2 차원 배열을 사용하여 정점 사이에 가장 짧은 경로 길이를 저장하고 각 반복 에이 배열을 업데이트합니다. 마지막으로 모든 정점 사이에서 가장 짧은 경로를 얻을 수 있습니다.
먼저, 2D 배열의 n x n 배열을 만들어야하며, 여기서 n은 그래프의 정점 수를 나타냅니다. 배열의 각 요소는 두 정점 사이의 거리를 나타내며, 두 정점 사이에 가장자리가없는 경우 거리가 무한대로 설정됩니다. 다음은 PHP 코드 구현입니다.
함수 flydwarshall ($ 그래프) {
$ n = count ($ 그래프);
$ dist = $ 그래프;
for ($ k = 0; $ k <$ n; $ k ++) {
for ($ i = 0; $ i <$ n; $ i ++) {
for ($ j = 0; $ j <$ n; $ j ++) {
if ($ dist [$ i] [$ k] + $ dist [$ k] [$ j] <$ dist [$ i] [$ j]) {
$ dist [$ i] [$ j] = $ dist [$ i] [$ k] + $ dist [$ k] [$ j];
}
}
}
}
return $ dist;
}
다음으로 예제 그래프를 정의하고 알고리즘을 테스트합니다. 우리는 인접성 행렬을 사용하여 그래프의 구조를 나타내며, 정점 사이의 거리를 2 차원 배열에 저장합니다. 샘플 코드는 다음과 같습니다.
$ 그래프 = [
[0, 5, inf, 10],
[Inf, 0, 3, inf],
[inf, inf, 0, 1],
[Inf, Inf, Inf, 0]
];
위의 예제 다이어그램에서 INF는 두 정점 사이에 가장자리가 없으며 거리가 매우 큰 값으로 설정됩니다. 이제 Floydwarshall 함수를 호출하여 가장 짧은 경로 배열을 계산할 수 있습니다.
$ result = floydwarshall ($ 그래프);
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
0 5 8 9 INF 0 3 4 Inf 0 1 Inf inf 0
위의 결과는 그림의 모든 정점 사이의 가장 짧은 경로 길이를 보여줍니다. 여기서 Inf는 두 정점 사이에 경로 연결이 없다는 것을 의미합니다.
이 기사는 PHP를 사용하여 Floyd-Warshall 알고리즘을 구현하여 그래프의 가장 짧은 경로 문제를 해결하는 방법을 소개합니다. 동적 프로그래밍이라는 아이디어를 사용하면 O의 시간 복잡성으로 그래프의 모든 정점 사이에서 가장 짧은 경로 길이를 찾을 수 있습니다 (n^3). 알고리즘 설계 기술을 합리적으로 사용함으로써 실제 문제를 해결하는 데이 알고리즘을 빠르고 효율적으로 적용 할 수 있습니다.
