关于最短路径的个人总结
1.dijkstra朴素算法
在算最短路径的时候可以用到的一个算法,常用于无负权边,稠密图,在朴素算法中用邻接矩阵来实现
时间复杂度为o(n^2)
算法思想:
每次找到一个最短路径的点,加入到已经确定的最短路径的集合中
实现过程:
通过n次遍历,每次加入一个点到最短路径的集合中,用st[N]来表示这个点是否存在集合中,找到不存在st中最短路径的点t中,把这个点放到st中,然后用t点的边 遍历更新所有点的距离
2.dijkstra堆优化算法
在算最短路径的时候可以用到的一个算法,常用于无负权边,稀疏图,在优化算法中用邻接表来实现
时间复杂度为o(nlngm)
算法思想:
每次找到一个最短路径的点,加入到已经确定的最短路径的集合中
为什么要用堆优化 : 如果是稀疏图的话,点的数量超过了1e4,用邻接矩阵就会爆,用堆优化之后,每次只需要找到有过更新的点即可,在查找这个过程时间复杂度从o(n)变成了o(1)
实现过程:
先把源点以及源点的距离放进优先队列中,然后先弹出再遍历该点的所有边,得到距离最短的下一个点,然后再把该点放进队列中,由于优先队列中队头元素是距离最小的点,在每次遍历完最短路径的点的时候,队头就是我们要找的下一个最短路径的点,弹出即可。在这个过程中,st数组用来标记已经完成最小路径寻找的点
小根堆优先队列写法
typedef pair[HTML_REMOVED] pii;
priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> q;
3.bellman-ford算法
如果边长为负数的时候,dijkstra算法就不行了,因为在dijkstra算法中如果边的数量增加,那么到这个点的距离必定会增加,就好比 1 -> 2 -> 3,如果变成了 1 -> 2 ->3 -> 4的话,距离是必定增加的,所以要用另一个方法去解决这个问题。
如果有行走的步数k次要求,那么可以用bellman-ford算法
时间复杂度o(nk)
算法思想:
遍历k次,每次更新最短边,在经过k此更新之后即可找到k次步数内走到target点的最短距离
4.spfa算法
如果为了寻找最短边,可以吧bellman-Ford算法中的k变成了n即可,但是问题也随之而来,如果n的数量级大于1e3,那么就非常容易爆数据,为了解决这个办法,我们用spfa算法实现
时间复杂度o(m),最坏o(nm);//m为边数
算法思想:
与dijkstra的堆优化思路有些类似,同样是用队列来实现,但是这个时候在队列中的元素是待确定的。先把源点入队,然后遍历源点的所有边,若是找到距离更新的点,则入队,在遍历完所有的边之后,就可以得到了最短路径长度。在这个时候st数组是用来标记是否在队列中
如果存在负权回路的话,要开一个cnt数组,去记录当前走的步数,如果一个点的步数超过n的话,根据抽屉原理,这个必定存在负权回路
关于spfa算法的补充:如果是无负边的图,数据量小的也可以用spfa算法过掉,比如在dijkstra I中,就可以用dijkstra算法解决该问题,只要数据量不超的情况下,最短路径问题可以用dijkstra算法解决
5.floyd算法
上述问题都是一源多汇的情况,如果是多源汇的情况,则需要用floyd算法
时间复杂度o(n^3)
算法思想:
经过三重遍历,dp思想,每次遍历经过一个点i的最短距离,遍历完后就可以得到整张图的最短距离
如第一次遍历完经过1点后,之后遍历经过2点时,如果需要经过1点的话,属于已经遍历完成的状态
代码实现:
for(int i=1;i<=n;i)
for(int j=1;j<=n;j)
for(int k=1;k<=n;k++)
g[j][k] = min(g[j][k] , g[j][i] + g[i][k] );
您判断负环的方法在有重边的情况下可能有问题吧(逃
在判断边的长度是否改变的时候,是用 cnt[j] = cnt[t] + 1的,而不是自加操作,就是上一个点的距离加1,所以重边不会对这个结果产生影响
抱歉,我有点不懂您的意思,能发一下代码吗?
请问此时的cnt数组的含义是什么呢?