Floyd-弗洛伊德算法
2024-08-24 22:12:48
今天,研究一下谁都能看懂的弗洛伊德算法。
首先,弗洛伊德算法是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。
这个算法需要一个用到一个二维数组啊a[][],而a[i][j]表示的就是,i到j的距离。
而在一个图中,可能会存在k,i到k再到j的距离可能会更短,也就是a[i][k]+a[k][j]<a[i][j]
(转)
如上图中,4到3的距离为12,但如果4先到1,再到3,距离就会缩短到5+6=11。再继续往后推,如果路线为4->1->2->3的话,距离会被缩短到5+2+3=10。这个时候,我们就可以把a[4][3]刷新成10了。
代码如下
for (int i=; i<=n; i++)
for (int j=; j<=n; j++)
for (int k=; k<=n; k++)
if (a[i][k]+a[k][j]<a[i][j])
a[i][j]=a[i][k]+a[k][j];
最新文章
- Web性能优化:基本思路和常用工具
- Pyinstaller打包Selenium脚本为exe文件执行问题
- ado.net 向sql中插入新数据的同时获取自增重的id值
- C/C++ 宏中的 #、#@、##的作用
- 泌尿系统 Excretory system
- 设置groupBox背景透明
- leetcode 133. Clone Graph ----- java
- Java检测文件是否UTF8编码
- android的休眠和唤醒流程
- 玩SSH,SFTP
- C++的运算符
- CDbConnection failed to open the DB connection: SQLSTATE[28000] [1045] Access denied for user &#39;root&#39;@&#39;localhost&#39; (using password: YES)
- 初学python之路-day12
- Python面向对象1:类与对象
- 一起学Hive——详解四种导入数据的方式
- 自动化测试-9.selenium多窗口句柄的切换
- jquery.fn.extend与jquery.extend用法与区别
- html 居中的内容显示框
- Node.js压缩与解压数据
- Pyhton 编程风格
热门文章
- react router路由传参
- jQuery.getJSON跨域访问的正确使用方式(史上最傻瓜式解释)
- 在JS中,一切东东其实都是对象
- [POJ2777] Count Color
- saltshaker填坑
- 对Office文档进行授权
- tomcat work目录
- HDU1596 find the safest road---(最短路径dijkstra,#变形#)
- finally return 执行顺序问题
- 【BZOJ2286】【SDOI2011】消耗战 [虚树][树形DP]