dijkstra算法为什么不能处理带有负边权的图
2024-09-06 20:59:09
| 1 | 2 | 3 | |
| 1 | 0 | 8 | 9 |
| 2 | 10 | 0 | 10 |
| 3 | 10 | -2 | 0 |
先看样例再解释，看邻接矩阵会发现， 如果用dijkstra算1-2的最短路因为贪心思想所以得到的结果是8，但明显可以看到1-3-2最短，结果为7；这是为什么呢？
因为dijkstra用了贪心的思想，每次选取的是当前最短的边进行松弛，当边都是正权时，松弛后边权一定比当前最短边大，所以满足贪心的条件，有了负边后不满足贪心的条件所以不能用dijkstra计算带有负边的单源最短路
最新文章
- ios 真机调试 could not find Developer Disk Image
- 特征的SID表、M表、P表、Q表、X表、Y表、T表
- 定时组件quartz系列<一>模拟定时组件小程序
- Java之对象序列化和反序列化
- python学习第一天内容整理
- rhel 6.7 离线安装docker
- 从SQL Server数据库转到Oracle数据库的数据脚本处理
- os系统
- 大文件视频断点续传插件resumabel.js，优化上传速度，缩短最后一片等待时长。
- xampp集成环境下重置mysql的密码
- PDO连接mysql数据库加载慢
- 6、Spring-Kafka4
- MySQL 5.7.14 net start mysql 服务无法启动
- export / import 温故而知新
- zlib交叉编译
- kbmmw 5.01 发布
- $.ajax的一些总结
- ios中Pldatabase的用法(2)
- freetds 移植
- DataSet转化为实体类【转】