笔灵AI论文写作三步搞定，GO>>
最短路径编程算法脑图思维导图
免费下载
免费使用文件
生杀予夺 浏览量：82023-12-03 14:23:37
已被使用0次
数据编程软件最短路径相关内容讲解
树图思维导图提供 最短路径编程算法脑图 在线思维导图免费制作，点击“编辑”按钮，可对 最短路径编程算法脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：595fd7c233bc083d24be62240f140add
思维导图大纲
最短路径思维导图模板大纲
单源最短路径——BFS
就是对BFS的一个小修改，在visit一个顶点时，修改其最短路径长度d[]，并在path[]记录前驱结点
最短路径的广度生成树一定是高度最小的生成树
各顶点最短路径：Floyd算法
基本思想
使用动态规划思想，求每一对顶点之间的最短路径
若不允许中转，则最短路径？
若允许在v0中转，则最短路径为？
若允许在V0，V1中转，则最短路径为？……
动态规划实现
动态规划思想
代码实现
总结
一图胜千言
单源最短路径：Dijkstra算法
算法实现思想
final[]标记各顶点是否已找到最短路径；dist[]标记最短路径长度；path[]标记路径上的前驱
循环遍历所有顶点，找到还没确定最短路径且dist最小的顶点vi，final[i] = true;
检查所有邻接自vi的顶点，若其final值为false，更新dist和path；
循环处理上述两条n-1次
Dijkstra算法过程详解
和Prim算法的异同
相同之处
都是贪心算法，都是逐步递增求解过程
不同之处
用途不同
Dijikstra用于求带权图单元最短路径
Prim求带权图最小生成树
算法实现过程不同
Dijkstra贪婪地选择与源点v0最近的下一条边
而Prim贪婪地选择与已加入MST中任意顶点最近的下一条边
因此Dijkstra可以产生树，但未必是最小生成树MST
限制不同
Dijkstra限制边上权值非负，Prim没有这个限制
沪公网安备 31011502019485号
上海工商