플로이드 알고리즘의 원리는 무엇입니까?

플로이드 알고리즘의 원리는 주어진 가중치 그래프에서 여러 소스 지점 사이의 최단 경로를 찾기 위해 동적 프로그래밍 아이디어를 사용하는 알고리즘입니다. 이는 Dijkstra의 알고리즘과 유사합니다. 양수 또는 음수 에지 가중치. 최단 경로 알고리즘.

Floyd算法 보간점 방법이라고도 알려진 이 알고리즘은 Dijkstra 알고리즘과 유사하게 주어진 가중치 그래프에서 여러 소스 점 사이의 최단 경로를 찾기 위해 동적 계획법의 아이디어를 사용하는 알고리즘입니다. 알고리즘의 이름은 창시자 중 한 명이자 1978년 튜링상 수상자이자 스탠포드 대학교 컴퓨터 과학 교수인 로버트 플로이드의 이름을 따서 명명되었습니다.

컴퓨터 과학에서 플로이드-워샬 알고리즘은 양수 또는 음수 에지를 갖는 방법입니다. 가중치가 있는(그러나 음의 순환이 없는) 가중치 그래프에서 최단 경로를 찾는 알고리즘입니다. 알고리즘을 한 번 실행하면 모든 정점 쌍 사이의 최단 경로 길이(가중치)를 찾습니다. 경로 자체의 세부 정보를 반환하지는 않지만 알고리즘을 간단히 수정하면 경로를 재구성할 수 있습니다. 이 알고리즘의 버전은 관계 R의 전이적 폐쇄 또는 (Schulze 투표 시스템과 관련하여) 가중치 그래프의 모든 정점 쌍 사이의 가장 넓은 경로를 찾는 데 사용될 수도 있습니다.

Floyd-Warshall 알고리즘은 동적 프로그래밍의 한 예이며 1962년 Robert Floyd가 현재 허용하는 형식으로 출판되었습니다. 그러나 이는 본질적으로 1959년 Bernard Roy와 1962년 Stephen Warshall이 발표한 그래프의 전이적 폐쇄를 찾는 알고리즘과 동일하며 결정론적 유한 오토마타를 정규식으로 변환하기 위한 Kleene의 1956년 알고리즘과 밀접하게 관련되어 있습니다. 세 개의 중첩된 for 루프로 구성된 현대적인 알고리즘 공식은 1962년 Peter Ingerman에 의해 처음 설명되었습니다.

이 알고리즘은 Floyd 알고리즘, Roy-Warshall 알고리즘, Roy-Floyd 알고리즘 또는 WFI 알고리즘이라고도 합니다.

Core Idea Editor

1. 경로 행렬

가중 행렬을 통해 그래프의 각 두 점 사이의 최단 경로 행렬을 찾습니다.

그래프의 가중 인접 행렬 A=[a(i,j)] n×n에서 시작하여 n 업데이트를 반복적으로 수행합니다. 즉, 행렬 D(0)=A에서 공식에 따라 행렬 D( 1); 그리고 동일한 공식을 사용하여 D(1);...;에서 D(2)를 구성합니다. 마지막으로 동일한 공식을 사용하여 D(n-1)에서 행렬 D(n)을 구성합니다. 행렬 D(n)의 i행과 j열의 요소는 정점 i에서 정점 j까지의 최단 경로 길이입니다. 동시에, 후속 노드 행렬 경로는 그래프의 거리 행렬이라고 합니다. 또한 두 지점 사이의 거리를 기록하는 방법도 도입되었습니다.

이완 기술(이완 작업)을 사용하여 i와 j 사이의 다른 모든 지점을 이완하세요. 따라서 시간 복잡도는 O(n^3);

2입니다. 상태 전이 방정식

상태 전이 방정식은 다음과 같습니다: map[i,j]:=min{map[i,k]+map [k, j], map[i,j]};

map[i,j]는 i에서 j까지의 최단 거리를 나타내며, K는 전체 i,j에 대한 중단점이며, map[n, n]은 0이어야 하고, 아니면 질문의 의미에 따라 하십시오.

물론, 이 도로에 접근할 수 없는 경우에는 지도[i,k] 도로가 없는 등 특별한 처리가 이루어져야 합니다.

알고리즘 프로세스 편집기

1, 모든 일방적 경로에서 시작하세요. 두 점 사이의 거리는 모서리의 가중치입니다. 두 점을 연결하는 모서리가 없으면 가중치는 무한합니다.

2. 정점 u와 v의 각 쌍에 대해 u에서 w, v까지의 경로가 알려진 경로보다 짧은 정점 w가 있는지 확인하세요. 그렇다면 업데이트하세요.

그래프를 인접 행렬 G로 표현합니다. Vi에서 Vj까지 도달할 수 있는 도로가 있으면 G[i][j]=d, d는 도로의 길이를 나타냅니다. 그렇지 않으면 G[i][j]= 무한대. 삽입된 점의 정보를 기록하기 위해 행렬 D를 정의합니다. D[i][j]는 Vi에서 Vj로 전달되어야 하는 점을 나타냅니다. D[i][j]=j를 초기화합니다. 각 꼭지점을 그래프에 삽입하고 삽입 후의 거리를 원래 거리와 비교합니다. G[i][j] = min( G[i][j], G[i][k]+G[k][j ] ), G[i][j]의 값이 작아지면 D[i][j]=k가 됩니다. G에는 두 지점 사이의 최단 경로 정보가 포함되고, D에는 최단 경로 정보가 포함됩니다.

예를 들어 V5에서 V1까지의 경로를 찾고 싶습니다. D에 따르면 D(5,1)=3이면 V5에서 V1까지의 경로가 V3를 통과한다는 의미이며 D(5,3)=3이면 V5와 V3을 의미합니다. V3이 직접 연결되어 있습니다. D(3,1)=1이면 V3과 V1이 직접 연결되어 있음을 나타냅니다.

시간 복잡도 및 공간 복잡도 편집

시간 복잡도: O(n^3);

공간 복잡도: O(n^2)

장점 및 단점 분석 및 편집

Floyd 알고리즘 적용 가능 기반 APSP(All pairs Shortest Paths, multi-source shortest path)에서는 조밀한 그래프에 가장 좋은 영향을 미치는 동적 프로그래밍 알고리즘이며 간선 가중치는 양수 또는 음수일 수 있습니다. 이 알고리즘은 간결한 삼중 루프 구조로 인해 밀도가 높은 그래프의 경우 Dijkstra 알고리즘의 |V| 실행보다 효율성이 높고 SPFA 알고리즘의 |V| 실행보다 높습니다.

장점: 이해하기 쉽고, 두 노드 사이의 최단 거리를 계산할 수 있으며, 코드 작성이 간단합니다.

단점: 시간복잡도가 상대적으로 높아 대용량 데이터 계산에는 적합하지 않습니다.

위 내용은 플로이드 알고리즘의 원리는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!