摘要现实生活中许多实际问题的解决依赖于最短路径的应用，其中比较常用的是 floyd算法。通过 floyd 算法使最短路径问题变得简单化.采纳图的邻接矩阵或邻接表实现最短路径问题中图的存储。采纳 Visual C++6。0 的控制台工程和 MFC 工程分别实现基于floyd 算法求最短路径的应用。关键词:最短路径;floyd 算法；邻接矩阵；MFC 工程目录1 需求分析 12 算法基本原理 1 2 。 1 邻接矩阵 1 2.2 弗洛伊德算法 1 3 类设计 2 3.1 类的概述 2 3 。 2 类的接口设计 3 3.3 类的实现 3 4 基于控制台的应用程序 6 4.1 主函数设计 6 4 。 2 运行结果及分析 6 5 基于 MFC 的应用程序 7 5.1 图形界面设计 7 5.1 程序代码设计 7 5 。 3 运行结果及分析 14 结论 14 参考文献 15 1 需求分析Floyd 算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978 年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。假若要在计算机上建立一个交通咨询系统则可以采纳图的结构来表示实际的交通网络。这个资讯系统可以回答游客提出的各种问题。例如,一位旅客要从 A 城到 B 城，他希望选择一条途中中转次数最少的路线。假设图中每一站都需要换车，则这个问题反映到图上就是要找一条从顶点 A 到 B 所含边的数目最少的路径。我们只需从顶点 A出发对图作广度优先搜索，一旦遇到顶点 B 就终止。由此所得广度优先生成树上，从根顶点 A 到顶点 B 的路径就是中转次数最少的路径，路径上 A 与 B 之间的顶点就是途径中的中转站数。但是这只是一类最简单的图的最短路径的问题。有时对于旅客来说,可能更关怀的是节约交通费用;对于司机来说里程和速度则是他们感兴趣的信息。为了在图上标示有关信息可对边赋以权的值，权的值表示两城市间的距离，或图中所需时间，或交通费用等等。此时路径长度的量度就不再是路径上边的数目,而是路径上边的权值之和.边赋以权值之后再结合最短路径算法来解决这些实际问题。Floyd 算法是最短路径经典算法中形式较为简单，便于理解的一种。2 算法基本原理2。1 邻接矩阵邻接矩阵(Adjacency Matrix）：是表示顶点之间相邻关系的矩阵。设 G=(V，E）是一个图,其中 V={v1,v2，…，vn}。G 的邻接矩阵是一个具有下列性质的 n 阶方阵:(1）对无向图而言,邻接矩阵一定是对称的，而且对角线一定为零（在此...
