vc++商店选址最短路径floyd算法设计实现（含源代码）.doc

PAGE 2008/2009学年度第二学期 《数据结构》 课程设计说明书 题 目： 商店选址问题 班 级： 姓 名： 学 号： 指导教师： 日 期：2009-6-22~2009-6-26 计算机与信息工程系 第 1 页 1、问题描述 对于某一商店，其他各单位到其的距离不同，同时各单位人员去商店的频度也不同。请为商店选址，要求实现总体最优。 2、需求分析 核心问题: 求最短路径(选址的要求就是商店到各单位权值之和最少) 数据模型（逻辑结构）: 带权有向图 (权值计算: 距离*频度) 存储结构: typedef struct { string vexs[MAX_VERTEX_SIZE]; int arcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE]; int vexnum;// ,arcnum; }MGraph; 核心算法: Floyd算法(弗洛伊德算法-每一对顶点之间的最短路径) 输入数据: 各单位名称，距离，频度，单位个数． 输出数据: 所选单位名称． 总体思路:　如果商店是要选在某个单位，那么先用floyd算法得出各顶点间的最短距离/最小权值。 假设顶点个数有n个，那么就得到n*n的一张表格，arcs(i,j)表示i单位到j单位的最短距离/最小权值 , 这张表格中和最小的那一行(假设为第t行)，那么商店选在t单位处就是最优解。 3、开发环境 硬件环境：PC兼容机 软件环境：Visual C++ 6.0 操作系统：Windows 2000 4、算法设计思想 　Floyd算法利用动态规划思想，通过把问题分解为子问题来解决任意两点见的最短路径问题。设G=(V, E, w)是一个带权有向图，其边V={v1, v2, …, vn}。对于k≤n，考虑其结点V的一个子集。对于V中任何两个结点vi、vj，考虑从vi到vj的中间结点都在vk中的所有路径，设是其中最短的，并设的路径长度为。如果结点vk不在从vi到vj的最短路径上，则；反之则可以把分为两段，其中一段从vi到vk，另一段从vk到vj，这样便得到表达式。上述讨论可以归纳为如下递归式： 　　原问题转化为对每个i和j求，或者说求矩阵。 利用上述递归表达式，串行Floyd算法可以写成下面的样子： a）初始化：D[u,v]=A[u,v] 　　b)　For k:=1 to n 　　 For i:=1 to n 　　 For j:=1 to n 　　 If D[i,j]D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j]; 　　c)　算法结束：D即为所有点对的最短路径矩阵 算法包括三个循环，每个循环需要运行步骤n，最内部的循环体可以在常数时间内完成，因此算法的复杂度为：O(n^3)。 5、流程图 开始 开始 M Main（） 输入基本信息 输入基本信息 GreatMgraph（Gh） GreatMgraph（Gh） 建立邻接矩阵的存储结构 建立邻接矩阵的存储结构 Floyd算法 Floyd算法 N N YA[i][j]==INF,i!=j Y A[i][j]==INF,i!=j i到j不存在路径 i到j不存在路径 Floyed（Gh） Floyed（Gh） 输出i-j的路径和路径长度 输出i-j的路径和路径长度 输出超市的最佳地址：i 输出超市的最佳地址：i 结束 结束 6、课程设计过程中的关键算法 Floyd算法表述： 第一步，让所有路径加上中间顶点1，取A[i][j]与A[i][1]+A[1][j]中较小的值作A[i][j]的新值，完成后得到A(1),如此进行下去，当第k步完成后，A（k）[i][j]表示从i到就且路径上的中间顶点的路径的序号小于或等于k的最短路径长度。当第n-1步完成后，得到A（n-1），A（n-1）即所求结果。A（n-1）[i][j]表示从i到j且路径上的中点顶点的序号小于或等于n-1的最短路径长度，即A(n-1)[i][j]表示从i到j的最短路径长度。 代码表示如下： void Floyed(Mgraph *G) //带权有向图求最短路径floyd算法 { int A[MAXVEX][MAXVEX