1. 最短路

1.1 单源最短路Dijkstra算法

求某个点到所有其他点的最短路程

类似prim算法 从源点出发 每次贪心地扩大一个节点

维护一个表即可 第一列列为除了选中点的其余目标点, 第一行表轮次 如 第一次 第二次

第一次初始化 一行一行看,每次仅允许从已有 点团/集 到其余所有点走一步的距离

1->2 1->3 1->4

将1到其余点路程中最短的那个保留下来,例如 1到2比1到3 1到4更近,那么把2纳入点团/集

得到{1,2},然后再贪心地找1, 2 这个集使得1到其他点更短的路径 .保留最短的那条路对应的点,纳入点集 ,继续

1.2 多源最短路Floyd算法

求任意两点最短路程

最后要得到一个最短路矩阵 类似邻接矩阵

思想很漂亮,每次允许经过1个点,看此次情况是否部分好于上次,如果部分好于上次,保留更优的结果

初始化 不允许经过任何点.

如果有N个点 那么就是N阶矩阵 要重复N次 第一次允许通过1 第二次只允许通过2 第三次..只允许3

2. 求无向图的最小生成树算法

2.1 Kruskal算法

从顶点出发,任意一个皆可 连接最小权的边,保证不要成环,然后将连接的两点视为整体 继续找下一条边,这个类似单源最短路dijkstra 但是注意 这个不需要从源点计算距离,整体就是整体 距离是新的点到整体的距离

2.2 Prim算法

从边出发,全局找到一个最小边,连起来 保证不要成环,然后继续连最小权边