SPFA算法O(kE)
2024-09-04 11:06:08
SPFA算法O(kE)
Dijkstra和Floyed是不断的试点。Dijkstra试最优点，Floyed试所有点。
Bellman-Ford和SPFA是不断的试边。Bellman-Ford是盲目的试所有边，SPFA只试那些有利用价值的点的边。
两点说明：
1、因为dis[v]都为无穷大，所以可以保证每个点都进过一次队列。
2、当点有利用价值的话我们就把它丢进队列，没有的话就不丢进去，而且有些点的价值不是一次就消耗完了，所以需要被多次放入队列。
3、SPFA算法虽然是Bellman-Ford的优化，但是算法的写法却是和BFS很像。其实换个角度，他们都是搜索，算法的本质是一样的。
打个形象的比喻：
相当与现在要调查一起犯罪案，我手里现在抓到了一个嫌疑犯。我要通过这个嫌疑犯找到所有的罪犯。因为罪犯之间是有关联的（搜索那个罪犯的关系网，也就是搜索那一条条边。），
我首先把和第一个嫌疑犯有关的嫌疑犯都找到，然后对每个找到的嫌疑犯我都把所有和他相关联的嫌疑犯找到，因为新的嫌疑犯可能会供出之前嫌疑犯的更大恶行，
所以我就又要重新审问那个之前的嫌疑犯，把和他有关的嫌疑犯再找一遍。
最新文章
- GAME AI Pro 1 第1章
- 计划任务,机器码与注册码,Web服务
- lucene-Field.Store解析
- codeblocks+Mingw 下配置开源c++单元测试工具 google test
- 介绍 .Net工具Code Snippet 与 Sql Server2008工具SSMS Tools Pack
- 跟着鸟哥学Linux系列笔记2-第10章VIM学习
- 利用Columnal网格系统快速搭建网站的基本布局结构
- Delphi 如何清除动态数组的内存？
- 实战微信JS SDK开发：贺卡制作与播放（1)
- Python命名规范
- Java入门到精通——工具篇之Maven概述
- _CrtIsValidPointer 问题
- 【转】G40-70、G50-70联想小新笔记本SR1000随机Linux改Windows 7系统操作指导
- QF——iOS的单例模式
- Windows下Apache添加SSL模块
- 汇编语言2（mooc）
- 插入排序Insertion Sort
- MYSQL之库操作
- HDU 6108(整除判断 数学)
- MySQL信息提示不是英文问题