Floyd 알고리즘 : 다중 소스의 가장 짧은 경로를 해결하고 모든 노드와 나머지 노드 사이의 가장 짧은 거리를 계산하는 데 사용됩니다.
이 알고리즘의 아이디어는 먼저 거리 매트릭스를 초기화 한 다음 첫 번째 지점에서 시작하는 행렬 포인트 값을 점차 업데이트합니다. d [i] [j]는 지점 I에서 지점 j까지의 거리를 나타냅니다. K가 업데이트되면 d [i] [k]+d [k] [j] 및 d [i] [j]의 크기를 판단합니다. 전자가 작 으면이 값을 업데이트하십시오. 그렇지 않으면 변경되지 않습니다.
예를 들어 :
특정 Floyd 구현 알고리즘은 다음과 같습니다. [Java] 일반 사본보기
패키지 com.bliseang; 공개 클래스 Floyd {int [] [] 매트릭스; char [] 노드; 개인 최종 int inf = integer.max_value; public floyd (char [] 노드, int [] [] matrix) {this.nodes = 노드; this.matrix = 매트릭스; } public void floyd () {int [] [] 거리 = new int [nodes.length] [nodes.length]; // (int i = 0; i <nodes.length; i ++) {for (int j = 0; j <nodes.length; j ++) {거리 [i] [j] = matrix [i] [j]; }} // 루프 업데이트 업데이트 (int k = 0; k <nodes.length; k ++) {for (int i = 0; i <nodes.length; i ++) {for (int j = 0; inf : 거리 [i] [k] + 거리 [k] [j]; if (거리 [i] [j]> temp) {거리 [i] [j] = temp; }}}}} // Floyd의 가장 짧은 경로 System.out.printf ( "floyd : /n")의 결과를 인쇄합니다. for (int i = 0; i <nodes.length; i ++) {for (int j = 0; j <nodes.length; j ++) system.out.printf ( "%12d", 거리 [i] [j]); System.out.printf ( "/n"); }}} 구현 후 위의 그림의 포인트와 가중치에 대한 테스트가 제공됩니다.
패키지 com.bliseang; public class main {public static void main (String [] args) {int inf = integer.max_value; char [] 노드 = { '0', '1', '2', '3'}; int matrix [] [] = {/*a*//*b*//*c*//*d*//*a*/{0, 1, 2, 1},/*b*/{inf, 0, inf},/*c*/{inf, 3, 0, 1},/*d*/{inf, 1, 0},}; int [] dist = new int [nodes.length]; Floyd Floyd = New Floyd (노드, 매트릭스); floyd.floyd (); }}위는이 기사의 모든 내용입니다. 모든 사람의 학습에 도움이되기를 바랍니다. 모든 사람이 wulin.com을 더 지원하기를 바랍니다.