最小生成树最短路径问题.ppt

图 —— 最小生成树与最短路径问题 2009/05/14 基于邻接表的图操作运算 主要内容 生成树的概念（spanning tree） Prim算法 Kruskal算法 最短路径问题 Dijkstra算法 Floyd算法 无向图中无环的充要条件 检查每一个连通分枝 对于所有连通分枝： 顶点数 – 边的数目 = 1 可以采用周游算法。 算法复杂度：n 最小生成树 Minimum-cost Spanning Tree 连通无向带权图 —— 网络。 网络（带权图）的生成树中生成树各边的权值加起来称为生成树的权，把权值最小的生成树称为最小生成树。 (简称为MST)。 MST性质 G=(V，E)是一个网络，U是顶点集合V的一个真子集。 如果u∈U，v∈V-U，且边(u,v)是图G中所有一个端点在U里，另一端点在V-U里的边中权值最小的边， 则一定存在G的一棵最小生成树包括此边(u,v)。 MST必包含连通图中任意两个顶点划分之间的最小权的边。 （任意割集中的最小边） MST性质证明（反证法） 边(u,v)是图G中所有一个端点在U里，另一端点在V-U里的边中权值最小的边。 假设：存在G的一棵最小生成树不包括此边。 贪心算法一般思路 初态（起点） 候选对象集合 贪心选择算法（按当前状态） 可行评估函数 目标函数 Kruskal算法 例题∶用Kruskal方法构造图的最小生成树  ①初始时，T为只有6个顶点的非连通图。 ②边(v1, v2)的两个顶点v1，v2分别属于两个连通分量，将边(v1, v2)加入T。 ③同理，将边(v1, v3)加入T。 ④由于边(v2, v3)的两个顶点v2，v3属于同一个连通分量，因此，舍去这条边。 ⑤同理将边(v0, v1)、(v1, v5)加入T，边(v3, v5)舍去，边(v3, v4)加入T。 这时T中含的边数为5条，成为一个连通分量，T就是G的一棵最小生成树。 算法框架 最短路径问题 如果图中从一个顶点可以到达另一个顶点，则称这两个顶点间存在一条路径。从一个顶点到另一个顶点间可能存在多条路径，而每条路径上经过的边数并不一定相同。 如果图是一个带权图，则路径长度为路径上各边的权值的总和，两个顶点间路径长度最短的那条路径称为两个顶点间的最短路径，其路径长度称为最短路径长度。 Dijkstra算法 ——Single Source/All Destinations Dijkstra算法求解从顶点v0出发到其它各顶点最短路径。 基本思想 设置一个集合U，存放已求出最短路径的顶点，V-U是尚未确定最短路径的顶点集合。 每个顶点对应一个距离值，集合U中顶点的距离值是从顶点v0到该顶点的最短路径长度； 集合V-U中顶点的距离值是从顶点v0到该顶点的只包括集合U中顶点为中间顶点的最短路径长度。 初始状态： 处理框架： （1）在集合V-U中选择距离值最小的顶点vmin加入集合U； （2）对集合V-U中各顶点的距离值进行修正：如果加入顶点vmin为中间顶点后，使v0到vi的距离值比原来的距离值更小，则修改vi的距离值。 （3）重复（1）（2）操作，直到从v0出发可以到达的所有顶点都在集合U中为止。 存储结构 修正距离值的方法 如果加入顶点vmin为中间顶点后 dist[i].length dist[min].length + G.arcs[min][i] 则将顶点vi的距离值改为 dist[min].length + G.arcs[min][i] 并修改路径上vi的前趋顶点： dist[i].prevex = min 例子： 初始状态V = {v0} 结果dist[n]为{{0, 0}, {50, 0}, {10, 0}, {MAX, -1}, {45, 0}, {MAX, -1} } ②．在集合V-U中找出距离值最小的顶点v2，将顶点v2加入集合U中。 原：dist[n]为{{0, 0}, {50, 0}, {10, 0}, {MAX, -1}, {45, 0}, {MAX, -1} } 后：dist[n]为{{0, 0}, {50, 0}, {10, 0}, {25, 2}, {45, 0}, {MAX, -1} } （接）同理在集合V-U中找出当前距离值最小的顶点v3，并调整集合V-U中顶点的距离值。 最后： 在集合V-U中找出当前距离值最小的顶点v4。并调整集合V-U中顶点的距离值。 结果dist[n]为{{0, 0}, {45, 3}, {10, 0}, {25, 2}, {45, 0}, {MAX, -1} } 没有可以再加入集合U的顶