来源：学生作业帮 编辑：作业帮 分类：生物作业 时间：2024/07/17 22:17:25
图论中常见的最短路径算法有几种?都是什么?
只要列出有几种，分别是什么就行啦，嘻嘻~
主要是有三种、、
第一种是最直接的贪心dijkstra算法、、可以利用堆数据结构进行优化、、缺点就是不能求有负权的最短路与判断负环、、
第二种是bellman-ford算法、、根据松弛操作的性质是可以来判断负环的、、时间复杂度是O(nm)的、、
第三种是SPFA算法、、把他单独拿出来作为一种算法并不是非常好的、、他的实质应该是上面的bellman-ford算法的队列优化时间复杂度更低、O(KE)、K的值约等于2、、
作业帮