图论相关算法伪代码

朴素版的dijkstra()算法（适用于稠密图）O(n^2)：

首先把dist都初始化为0x3f3f3f3f，然后1号点dist置0，然后进行n - 1次循环更新剩余的n - 1个点到1号点距离。

循环内容：首先循环找到目前为止dist最小的一个点，然后用该点更新所有它可以到达的点。

最后如果n号点的dist距离仍为inf，则到达不了，否则输出dist[n]。邻接矩阵存放图。

堆优化版的dijkstra()算法（适用于稀疏图）O(mlogn)：

我们可以把距离与对应点的信息放到小根堆里面，优化朴素版本寻找min dist的步骤，然后借助队列更新dist数组。邻接表存放图。

定义小根堆: priority<PII,vector,greater> heap;

bellman_ford()算法(求限制步数的最短路问题) O(nm)：

如果步数限制为k，那么就循环k次，然后循环所有边，更新dist数组：dist[b] = min(dist[b], backup[a] + w);记得要用备份数组backup储存上一步的dist，以免发生串联

SPFA算法 一般O(m), 最坏O(nm)：

对bellman_ford算法做出的优化算法，用队列存放dist更新了的点，宽搜优化。用st数组存放点是否在队列中的状态，当dist更新的话，如果!st[i]，则更新st[i] = true;

图论相关算法伪代码

原文：https://www.cnblogs.com/scl0725/p/13993709.html