1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
| package com.atguigu.floyd;
import java.util.Arrays;
public class FloydAlgorithm {
public static void main(String[] args) { char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' }; int[][] matrix = new int[vertex.length][vertex.length]; final int N = 65535; matrix[0] = new int[] { 0, 5, 7, N, N, N, 2 }; matrix[1] = new int[] { 5, 0, N, 9, N, N, 3 }; matrix[2] = new int[] { 7, N, 0, N, 8, N, N }; matrix[3] = new int[] { N, 9, N, 0, N, 4, N }; matrix[4] = new int[] { N, N, 8, N, 0, 5, 4 }; matrix[5] = new int[] { N, N, N, 4, 5, 0, 6 }; matrix[6] = new int[] { 2, 3, N, N, 4, 6, 0 }; Graph graph = new Graph(vertex.length, matrix, vertex); graph.floyd(); graph.show(); }
}
class Graph { private char[] vertex; private int[][] dis; private int[][] pre; public Graph(int length, int[][] matrix, char[] vertex) { this.vertex = vertex; this.dis = matrix; this.pre = new int[length][length]; for (int i = 0; i < length; i++) { Arrays.fill(pre[i], i); } }
public void show() { char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' }; for (int k = 0; k < dis.length; k++) { for (int i = 0; i < dis.length; i++) { System.out.print(vertex[pre[k][i]] + " "); } System.out.println(); for (int i = 0; i < dis.length; i++) { System.out.print("("+vertex[k]+"µ½"+vertex[i]+"µÄ×î¶Ì·¾¶ÊÇ" + dis[k][i] + ") "); } System.out.println(); System.out.println();
}
} public void floyd() { int len = 0; for(int k = 0; k < dis.length; k++) { for(int i = 0; i < dis.length; i++) { for(int j = 0; j < dis.length; j++) { len = dis[i][k] + dis[k][j]; if(len < dis[i][j]) { dis[i][j] = len; pre[i][j] = pre[k][j]; } } } } } }
|