常用图论算法

本笔记总结一些常用的图论算法。 参考链接有： 笔记目录： 一般使用广度优先算法作为无权的最短路径算法。 最短路径算法求的是一个点到其余所有点的最短路径 基本步骤： 将所有点的距离 d 设为无穷大 挑选初始点 s，将 ds 设为 0，将 shortest 设为 0 找到所有距离为 d 为 shortest 的点，查找他们的邻接链表的下一个顶点 w，如果 dw 的值为无穷大，则将 dw 设为 shortest + 1 增加 shortest 的值，重复步骤 3，直到没有顶点的距离值为无穷大 在有权图中，常见的最短路径算法有 Dijkstra 算法 Floyd 算法 Dijkstra 算法 迪杰斯特拉 Dijkstra 算法：Dijkstra 算法适用于权值为正的的图 Dijkstra 算法属于单源算法，即只能求出 某点到其它点最短距离，并不能得出任意两点之间的最短距离。该算法类似于边上有权值的最短路径算法，其本质是 贪婪算法 ，贪婪算法一般分阶段求解一个问题，并且在每个阶段都把出现的当做是最好的去处理。 算法步骤： 将所有边初始化为无穷大 选择一个开始的顶点，添加到优先队列中 对于该点的所有邻接顶点进行判断，如果到该点的距离小于原先的值，则将该值进行更新 将该点所有邻接顶点添加到优先队列中 从优先队列中挑选出一个路径值最小的顶点，将其弹出，作为新的顶点，重复步骤 3，4，5 直到所有点都被处理过一次 Floyd 算法可以求出任意两点的最短距离 Dijkstra 算法适合于权值为正的情况下，若权值为负则不能使用，因为出现死循环。这时候我们需要计算每个顶点被处理的次数，当某个顶点已经处理过的话，就跳出该循环。 该算法的运行时间依赖对顶点的处理方法，我们必须妖绿顺序扫描顶点以找出最小值的算法。 可以将顶点存储在优先级队列中。 如果一个图有负价边， 问题在与，一个顶点 u 被声明是 known 的，那个可能从另一个 unknown 的顶点 v 有一条回到 u 的负的路径，在这样的情况下选取从 s 到 v 再回到 u 的路径要比直接从 s 到 u 但不通过 v 更好。 还有一种更简单的例子：假如一张图里有一个总长为负数的环，那么Dijkstra算法有可能会沿着这个环一直绕下去，绕到地老天荒...