762每一对顶点间的最短路径.ppt

7 6 2每一对顶点间的最短路径Dijkstra算法是求源点到其它顶点的最短路径 怎样求任意两个顶点之间的最短路径 我们可以把Dijkstra算执行n次 每次从不同的顶点开始 则算法时间复杂度为O n3 Floyd弗洛伊德给出了另一个算法 时间复杂度也是O n3 但是形式上简单些 从演示中看算法思想一个简单的图及其邻接矩阵如下 a b c 11 6 4 2 3 D 1 从上面的D 1 开始 对于每两个顶点u v 在D 1 中存储着一条路径u v 现在我们考察 试着把a加到u v的路径上能否 得到一条更短的路径 即如果u a a v u v的话 能够找到一条更短的路径 a b c 11 6 4 2 3 D 1 D 0 本来路径上源点或终点就有a的不必考虑 对角线上的也不必考虑 a b c 11 6 4 2 3 D 1 D 0 D b a D a c 6 11 D b c 2 所以如果从a绕 反而远 那么这一项不变 a b c 11 6 4 2 3 D 1 D 0 a b c 11 6 4 2 3 D 1 D 0 D c a D a b 3 4 D c b 所以如果从a绕 更近 那么应该更新 a b c 11 6 4 2 3 D 1 D 0 从上面的D 0 开始 对于每两个顶点u v 在D 0 中存储着一条路径u v 现在我们考察 试着把b加到u v的路径上能否 得到一条更短的路径 即如果u b b v u v的话 能够找到一条更短的路径 a b c 11 6 4 2 3 D 1 D 0 本来路径上源点或终点就有b的不必考虑 对角线上的也不必考虑 a b c 11 6 4 2 3 D 1 D 0 D a b D b c 6 D a c 所以如果从b绕 更近 那么应该更新 a b c 11 6 4 2 3 D 1 D 0 a b c 11 6 4 2 3 D 1 D 0 D c b D b a 7 6 D c a 3 所以如果从b绕 反而远 那么这一项不变 a b c 11 6 4 2 3 D 1 D 0 从上面的D 1 开始 对于每两个顶点u v 在D 1 中存储着一条路径u v 现在我们考察 试着把c加到u v的路径上能否 得到一条更短的路径 即如果u c c v u v的话 能够找到一条更短的路径 a b c 11 6 4 2 3 D 2 D 1 本来路径上源点或终点就有c的不必考虑 对角线上的也不必考虑 a b c 11 6 4 2 3 D 2 D 1 D a c D c b 6 7 D a b 4 所以如果从c绕 反而远 那么这一项不变 a b c 11 6 4 2 3 D 2 D 1 a b c 11 6 4 2 3 D 2 D 1 D b c D c a 2 3 D b a 6 所以如果从c绕 更近 那么应该更新 a b c 11 6 4 2 3 D 2 D 1 D b c D c a 2 3 D b a 5 所以如果从c绕 更近 那么应该更新 现在 已经把所有的顶点都试了一遍 算法结束 每两个顶点之间的路径如D 2 所示 D 2 采用图的邻接矩阵的存储结构怎样构造一个图 再次不赘述 直接给出floyd算法 voidMDNet Floyd CDC pDC typedefvectorpath 使用顺序表模板pathp max vertex num max vertex num p存放每对顶点之间的最短路径intD max vertex num max vertex num D存放每对顶点之间的最短路径值inti j k for i 1 i vex num i 初始化for j 1 j vex num j p i j push back i p i j push back j 顶点i和顶点j之间的路径初始时就是ij D i j arcs i j 路径值为边 i j 的权值 for k 1 k vex num k 对于每一个顶点都要试探for i 1 i vex num i for j 1 j vex num j 在顶点i和顶点j之间的路径上试探kif i j continue 对角线上的元素 即顶点自身之 间 不予考虑if D i k D k j D i j 发现更短的路径D i j D i k D k j 新的i j间的路径由两部分组成 p i k p k j p i j p i k for intm 1 m p k j size m p i j push back p k j m for i 1 i vex