摘要现实生活中许多实际问题的解决依赖于最短路径的应用，其中比较常用的是 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 之间的顶点就是途径中的中转站数
但是这只是一类最简单的图的最短路径的问题
有时对于旅客来说,可能更关怀的是节约交通费用;对于司机来说里程和速度则是他们感兴趣的信息
