
算法笔记_069:Floyd算法简单介绍(Java)
发布日期:2021-05-09 04:48:20
浏览次数:9
分类:博客文章
本文共 1918 字,大约阅读时间需要 6 分钟。
目录
1 问题描述
何为Floyd算法?
Floyd算法功能:给定一个加权连通图,求取从每一个顶点到其它所有顶点之间的最短距离。(PS:其实现功能也称完全最短路径问题)
Floyd算法思想:将顶点i到j的直接距离依次与顶点i到顶点j之间加入k个中间节点之后的距离进行比较,从中选出最短的一组距离,即为顶点i到顶点j的最短距离,然后重复上述步骤求取其它顶点之间的最短距离。
2 解决方案
2.1 使用Floyd算法得到最短距离示例
此处借用《算法设计与分析基础》第3版上一个插图:
其中,- D(0)表示不包含中间节点,即给定图的原始权重矩阵;
- D(1)表示加入一个中间节点a;
- D(2)表示在D(1)的基础上再加入一个中间节点b;
- D(3)表示在D(2)的基础上再加入一个中间节点c;
- D(4)表示在D(3)的基础上再加入一个中间节点d,这时就可得到最终结果。
每次加入一个中间节点后,都要更新所有顶点之间的最短距离,直到所有顶点均可以作为中间顶点之后,才算更新完毕,即可得到最终结果。
2.2 具体编码
Floyd是计算每对顶点间最短路径的经典算法,其采用的思想是动态规划法。
时间复杂度是雷打不动的O(n^3)。
注意,Floyd算法计算最短距离可以有负权值的边,但不能有权值和为负数的回路。
下面代码中所用图的数据便是2.1中示例图的数据。
具体代码如下:
package com.liuzhen.chapter9;public class Floyd { /* * 参数adjMatrix:给定连通图的权重矩阵,其中权重为-1表示两个顶点不能直接相连 * 函数功能:返回所有顶点之间的最短距离权重矩阵 */ public void getShortestPaths(int[][] adjMatrix) { for(int k = 0;k < adjMatrix.length;k++) { for(int i = 0;i < adjMatrix.length;i++) { for(int j = 0;j < adjMatrix.length;j++) { if(adjMatrix[i][k] != -1 && adjMatrix[k][j] != -1) { int temp = adjMatrix[i][k] + adjMatrix[k][j]; //含有中间节点k的顶点i到顶点j的距离 if(adjMatrix[i][j] == -1 || adjMatrix[i][j] > temp) adjMatrix[i][j] = temp; } } } } } public static void main(String[] args) { Floyd test = new Floyd(); int[][] adjMatrix = {{0,-1,3,-1}, {2,0,-1,-1}, {-1,7,0,1}, {6,-1,-1,0}}; test.getShortestPaths(adjMatrix); System.out.println("使用Floyd算法得到的所有顶点之间的最短距离权重矩阵为:"); for(int i = 0;i < adjMatrix.length;i++) { for(int j = 0;j < adjMatrix[0].length;j++) System.out.print(adjMatrix[i][j]+" "); System.out.println(); } }}
运行结果:
使用Floyd算法得到的所有顶点之间的最短距离权重矩阵为:0 10 3 4 2 0 5 6 7 7 0 1 6 16 9 0
参考资料:
1.《算法设计与分析基础》第3版 (美)Anany Levitin 著 潘彦 译
2.
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2025年04月08日 19时05分20秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
(数据科学学习手札27)sklearn数据集分割方法汇总
2019-03-06
(数据科学学习手札40)tensorflow实现LSTM时间序列预测
2019-03-06
从零开始学安全(十六)● Linux vim命令
2019-03-06
阿里巴巴Json工具-Fastjson教程
2019-03-06
Spring Cloud Gateway - 快速开始
2019-03-06
Java对象转JSON时如何动态的增删改查属性
2019-03-06
Python 面向对象进阶
2019-03-06
Linux常用统计命令之wc
2019-03-06
shell脚本里使用echo输出颜色
2019-03-06
并发编程——IO模型详解
2019-03-06
Java之封装,继承,多态
2019-03-06
wait()与notify()
2019-03-06
使用js打印时去除页眉页脚
2019-03-06
Spring security OAuth2.0认证授权学习第二天(基础概念-RBAC)
2019-03-06
ORA-00904: "FILED_TYPE": 标识符无效
2019-03-06
Android中定时执行任务的3种实现方法
2019-03-06
MapReduce实验
2019-03-06
java大数据最全课程学习笔记(1)--Hadoop简介和安装及伪分布式
2019-03-06
[apue] getopt 可能重排参数
2019-03-06
移动互联网恶意软件命名及分类
2019-03-06