最短路径问题八年级最短路径

最短路长和最短路径的区别最短路长指的是距离，包括直线和曲线，最短路径指的是直线距离
求解：图论中常见的最短路径算法有几种？都是什么？主要是有三种、、
第一种是最直接的贪心dijkstra算法、、可以利用堆数据结构进行优化、、缺点就是不能求有负权的最短路与判断负环、、
【最短路径问题八年级最短路径】第二种是bellman-ford算法、、根据松弛操作的性质是可以来判断负环的、、时间复杂度是O(nm)的、、
第三种是SPFA算法、、把他单独拿出来作为一种算法并不是非常好的、、他的实质应该是上面的bellman-ford算法的队列优化时间复杂度更低、O(KE)、K的值约等于2、、

文章插图
求出最短路径，要过程，用Dijkstra算法。。。从v1开始遍历
v2 = 2;
v3 = 5;
v2较小所以跳到v2
v3 = 4;
v4 = 6;
v5 = 8;
v3较小所以跳到v3
v4 = 5;
v6 = 7;
v4较小所以跳到v4
v6 = 6;
v7 = 9;
v6较小所以跳到v6
v7 = 8;
所以最后结果v1 - v7最短路径为v1-v2-v3-v4-v6-v7,最短路径长度为8

最短路径问题 八年级 最短路径

秒懂生活扩展阅读

最短路径问题八年级最短路径