lisl1233

最短路径

字符串(6) 最小生成树(2)

/ 注册

全部文章 / 最短路径（共5篇）

最短路径--Dijstra堆优化

最短路径----Dijstra堆优化单源最短路径(是速度最快且最稳定的算法，但不过只能求带有非负权图) 思路： Dijstra每次需要遍历所有的点，找到一个最小值，而堆优化则是利用小顶堆的优势，每次都将距离最短的点都放在队列的顶部，则无需每次遍历所有的点，这样所需的时间就更短。时间复杂度O(m...

2021-07-14

1 472

最短路径--spfa

最短路径----spfa 单源最短路径思路: spfa算法是bellman_ford的队列优化算法，bellman是枚举所有的边，所以其时间复杂度为O(nm)，而spfa则是只枚举之前改变了值的边，如果当前点被改变了值，则讲这个点放到队列当中去，如果已经在队列当中了，就不需要再次放入队列当中，然后...

2021-07-14

1 503

最短路径--Bellman_ford

最短路径Bellman_ford 单源最短路径思路：循环n-1次,每次寻找出经过k条边到达其余点的最短路径，每次都遍历更新其余所有点。时间复杂度O（nm）Code: #include<iostream> #include<memory.h> #include<cm...

2021-07-13

1 430

最短路径--Dijstra

最短路径----Dijstra 单源最短路径思路: 寻找一个确定离起点最近的点，并给他打上标记，再用这个点当为中间点去更新其余的点。用vis标记i点是否为已经确定的点用dis存放起点到每i点的最短距离时间复杂度O(n²)Code: #include<iostream> #includ...

2021-07-13

1 451

最短路径--floyed

最短路径----floyed 多元最短路径思路: 遍历全数组，看每个点是否可以松弛，如果可以，将松弛完与未松弛进行比较，取值最小的方式。时间复杂度O(n³) Code: #include<iostream> #include<cmath> #inclu...

2021-07-13

1 467