您现在的位置是:首页 > 后台技术 > 数据结构与算法数据结构与算法
弗洛伊德算法(图文)
第十三双眼睛2023-10-23【数据结构与算法】人已围观
简介弗洛伊德算法
弗洛伊德算法
package com.xingchen.day017; import java.util.Arrays; public class Florid { 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}; Grap grap = new Grap(vertex.length,matrix,vertex); grap.floyd(); grap.show(); } } class Grap { private char[] vertex;//顶点数组 private int[][] dis;//从各个顶点出发,到其他顶点的近距离 private int[][] pre;//到达各个顶点的前驱 public Grap(int length, int[][] matrix, char[] vertex) { this.vertex =vertex; this.dis = matrix; this.pre = new int[length][length]; //对pre进行初始化,存放的是前驱顶点的下标 for (int i = 0;i<length; i++) { Arrays.fill(pre[i], i); } } public void show() { 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(); } } public void floyd() { int len = 0;//变量保存距离 //从中间顶点的遍历,k为中间顶点的下标 for (int k = 0;k<dis.length; k++) { //从I顶点开始出发 for (int i=0; i<dis.length; i++) { //到达J顶点,经过的顶点 for (int j = 0;j<dis.length; j++) { len = dis[i][k] + dis[k][j]; if (len < dis[i][j]) {//如果len小于ij直连的距离,就更新 dis[i][j] = len; pre[i][j] = pre[k][j]; } } } } } } |
Tags:
很赞哦! ()
上一篇:迪杰斯特拉算法(图文)
下一篇:马踏棋盘(图文)