只学了一天,所以可能有些不到位,见谅
倩倩总结一下dikjstra、bellman_ford、spfa
手先
:
实现原理:应该都算贪心吧??
都是用 dist[u]+w 和dist[v] 比较
(u是一条边的起点,v是这条边的终点,w是边权)
(dist[i]指的是从起点1到点i的最短距离)
dist[u]+w 指的是1->u->v ,把这个和dist[v]比较
是判断 1->u->v这条路径的长度是否比 dist[v]更优秀(当前最优解)
如果更优,就更新,不优就跳过
dikjstra:通过已知的最短路点去扩展该点周围的点。
bellman_ford :暴力枚举并更新每一条最短路,只要重复的次数够多,最终就会求出所有的最短路
spfa:和dikjstra有点像,因为他们都是从起点这个已知的最短路点去扩展周围的点,但spfa利用队列,目的是只搜和起点联通的边。
算法细结:
dikjstra:除了起点1之外,如何找到其他的最短路? 由于我们的dikjstra算法只处理正权边,在当前扩展到的dist[i]值中,最小的值d[j]对应的点j是当前已经确定的 1->j 最短路,而在当前扩展到的dist[i]数组中找最小值,是一个动态的过程,也就是我们每次都要遍历一遍dist数组,所以用二叉堆优化就行了。
bellman_ford:只要重复的次数够多,所有的dist[i]都能被求出,因为只要有一个dist[i]确定了,其他的dist[j]也会逐渐确立,那么重复多少次算多呢? 答案是N-1次,因为最多有N-1条边。
至于重复多少次,就是求出离起点多远的点的说法我个人是不认同的。
之所以能这样求,是因为我们规定了每一次重复都必须在上一次的遍历结束的状态的基础上。
第0次遍历,只有dist[1]=0,只要我们拷贝第0次的dist数组,然后第一次更新用拷贝数组backup,
因为我们更新的条件是:backup[u]+w < dist[v],在第一次更新中,我们只能更新1相邻的点。
其他点的dist在0次时候都是无穷
就可以做到这一点。所以并不是遍历多少次就离多远。
spfa:几乎不变的更新思想,但是利用队列优化,每一次只更新与队列中的点相连的点,而队列中的第一个元素就是起点,所以我们只会更新与起点联通的点,这样就减少了一些没必要的点的枚举。因为这并不是一个完全联通的图。
所以在一些分叉不多的图中,spfa的复杂度是近乎线性的,但在网格图这种四面八方都联通的图,差不多是 O(nm)的
判断负环,
bellman_ford 和 spfa都可以判断负环
对于bellman_ford,我们只需要求完最短路只后,再对每一条边进行遍历。查询一下是否能再更新,如果还能更新,说明有负环。
bellman_ford判负环的好处就是,不用去单独考虑负环是否与起点联通,因为bellman_ford算法是遍历所有边
spfa判负环,如果不加入特判的话,我们只能判与起点联通的负环。
所以我们需要将每个点都加入队列,这样的作用就是每个点都能作为起点,来更新与他们联通的点。
如果存在负环的话,说明这个环内的点会经常加入队列然后被删除,
我们只需要记录并更新一下每个点出现的次数,如果次数大于某个值就可以判断是负环了,不必一直循环。
这个值就是这个联通块的元素个数,不严格为n
只有当这个图强联通的时候,才是n
但是用n当这个值也是可以的。
关于建图问题:
dikjstra 和 spfa 都是以点为单位搜索的,所以我们正常建立邻接表即可
而bellman_ford是以边为单位枚举,所以我们不能建立邻接表,随便建立一个结构体,存起点终点和边权就行了
总结结束。。。。。暂时不学算法基础课了,等我abc和cf遇到新算法再说。
没事就写蓝书就行了。
写的非常好呀,但纠正一个一个小错误,bellman和spfa不是基于贪心的,而是基于迭代的(虽然我也不知道怎么证明迭代的正确性
我以为迭代就是暴力呢,所以就没特地写
在网吧打的。。。我得回家了