floyd算法2.ppt

组长:魏晓卡 组员：李丹 魏蕾 王丹 弗洛伊德算法 弗洛伊德算法 弗洛伊德算法的基本思想 * (1)给出网络的邻接矩阵D，令D(0)=D,其元素为dij(0) 邻接矩阵 * v1 V3 V4 V2 2 6 1 8 4 图1 弗洛伊德算法的基本思想 (2)在原路径里增加一个新结点，如果产生的新路径比原路径更小，则用新路径值代替原路径的值。这样依次产生n个矩阵（n为网络结点数） 用公式表示就是，对于K=1,2,3…n,第k个矩阵 运算过程中K从1开始，而 i，j 则分别从1到n取遍所有值，然后k加1，直到k等于n时停止。 * 弗洛伊德算法演示 A B D C 1 2 3 2 2 7 1 长度 0 1 2 3 0 0 1 ∞ 7 1 2 0 2 ∞ 2 ∞ ∞ 0 2 3 1 3 ∞ 0 路径 0 1 2 3 0 AB AD 1 BA BC 2 CD 3 DA DB 0 3 2 1 * A B D C 1 2 3 2 2 7 1 0 3 2 1 长度 0 1 2 3 0 0 1 ∞ 7 1 2 0 2 2 ∞ ∞ 0 2 3 1 ∞ 0 路径 0 1 2 3 0 AB AD 1 BA BC 2 CD 3 DA 9 ∞ 2 3 BAD DAB 弗洛伊德算法演示 * A B D C 1 2 3 2 2 7 1 0 3 2 1 长度 0 1 2 3 0 0 1 7 1 2 0 2 9 2 ∞ ∞ 0 2 3 1 2 0 路径 0 1 2 3 0 AB AD 1 BA BC BAD 2 CD 3 DA ∞ 3 ∞ 4 ABC DABC DAB 弗洛伊德算法演示 * A B D C 1 2 3 2 2 7 1 0 3 2 1 长度 0 1 2 3 0 0 1 3 1 2 0 2 2 ∞ ∞ 0 2 3 1 2 4 0 路径 0 1 2 3 0 AB ABC 1 BA BC 2 CD 3 DA DAB DABC 7 9 5 4 ABCD BCD AD BAD 弗洛伊德算法演示 * FLOYD算法步骤 算法：FLOYD 输入: 维矩阵 ，其中有向图 中的边 的长度为 。 输出: 矩阵 ，使得 等于 i 到 j 的最短路径长度。 (step 0) D ? l ; //将有向网的邻接矩阵输入到D中 (step 1) for k = 1 to n (step 3) for i = 1 to n (step 5) D[i, j] = min{D[i, j], D[i, k] + D[k, j]} (step 6) end for (step 8) end for (step 4) for j = 1 to n (step 7) end for 算法复杂度为　 O(n^3) 简单例子-》超市选址问题 问题描述 对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。 需求分析 核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少) 数据模型（逻辑结构）: 带权有向图 (权值计算: 距离*频度) 存储结构: typedef struct { string vexs[MAX_VERTEX_SIZE]; int arcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE]; int vexnum;// ,arcnum; }MGraph; 核心算法: Floyd算法(弗洛伊德算法-每一对顶点之间的最短路径) 输入数据: 各单位名称，距离，频度，单位个数． 输出数据: 所选单位名称． 总体思路:　 如果超市是要选在某个单位，那么先用floy算法得出各顶点间的最短距离/最小权值。 假设顶点个数有n个，那么就得到n*n的一张表格，arcs(i,j)表示i单位到j单位的最短距离/最小权值 , 这张表格中和最小的那一行(假设为第t行)，那么超市选在t单位处就是最优解。 * 算法小结 * Thanks！ * * * * *