朴素dijkstra
- 用邻接矩阵存储
第一步
初始化:
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
第二步
进行n - 1次迭代, 为了确定每个点的最终dist[i]
值
第三步
在循环中,进行二次迭代找出最小dist[j]
,并进行标记true
第三步
以该点j
进行对其他点松弛
第四步
返回dist[n]
,并判断是否dist[n] == inf
堆优化dijkstra
- 用邻接表存储
第一步
初始化
定义一个小顶堆,堆保存PII
,first
为 distance
, second
为ver
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
将点1
入队
第二步
取出堆顶,若st[ver] = true; 则 continue;
用堆顶的点更新其他的点,若被更新,将其入队
第三步
return dist[n]
, 最后判断是否dist[n] == inf
bellman_ford
- 用struct存储每一条边,
edge = {a, b, c}
第一步
初始化
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
第二步
进行k
次迭代,定义一个backup
数组,用于保存上一状态距离状况。 (维持步数)
第三步
在每一次迭代中,枚举每一条边,进行松弛
第四步
return dist[n]
,判断是否dist[n] > inf / 2
spfa
- 用邻接表存储
第一步
初始化
定义队列
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
并将1
入队,并标记st[1] = true
第二步
将队头t
出队,并st[t] = false
第三步
以点对它的连边进行松弛
若能松弛,则更新dist[j] = dist[t] + w[i]
在能松弛的前提下,若st[j] = false
(未入队),则将j
入队, 并标记true
第四步
return dist[n]
, 判断是否dist[n] == inf
Flyod
- 邻接矩阵存储
第一步
初始化图
g[][]
双重循环初始化,若i == j
初始化为0,反之为inf
第二步
直接上三重循环
第三步
判断是否dist[n] > inf / 2
这是五种 < 3
hh,
dijkstra
归为了一种,都一样~