基于Floyd算法的最短路径问题的求解c++1.doc

沈阳理工大学课程设计专用纸

PAGEII

摘要
现实生活中许多实际问题的解决依赖于最短路径的应用，其中比较常用的是floyd算法。通过floyd算法使最短路径问题变得简单化.采用图的邻接矩阵或邻接表实现最短路径问题中图的存储。采用VisualC++6。0的控制台工程和MFC工程分别实现基于floyd算法求最短路径的应用。
关键词:最短路径;floyd算法；邻接矩阵；MFC工程
目录
TOC\o”1—3”\h\z\uHYPERLINK\l"_Toc407713813”1需求分析PAGEREF_Toc407713813\h1
HYPERLINK\l”_Toc407713814”2算法基本原理PAGEREF_Toc407713814\h1
HYPERLINK\l”_Toc407713815”2。1邻接矩阵PAGEREF_Toc407713815\h1
HYPERLINK\l"_Toc407713816”2.2弗洛伊德算法PAGEREF_Toc407713816\h2
HYPERLINK\l”_Toc407713817"3类设计PAGEREF_Toc407713817\h2
HYPERLINK\l"_Toc407713818”3.1类的概述PAGEREF_Toc407713818\h2
HYPERLINK\l"_Toc407713819”3。2类的接口设计PAGEREF_Toc407713819\h3
HYPERLINK\l”_Toc407713820”3.3类的实现PAGEREF_Toc407713820\h4
HYPERLINK\l"_Toc407713821”4基于控制台的应用程序PAGEREF_Toc407713821\h7
HYPERLINK\l”_Toc407713822”4.1主函数设计PAGEREF_Toc407713822\h7
HYPERLINK\l"_Toc407713823"4。2运行结果及分析PAGEREF_Toc407713823\h8
HYPERLINK\l”_Toc407713824”5基于MFC的应用程序PAGEREF_Toc407713824\h9
HYPERLINK\l"_Toc407713825”5.1图形界面设计PAGEREF_Toc407713825\h9
HYPERLINK\l"_Toc407713826"5.1程序代码设计PAGEREF_Toc407713826\h11
HYPERLINK\l"_Toc407713827”5。3运行结果及分析PAGEREF_Toc407713827\h20
HYPERLINK\l"_Toc407713828”结论PAGEREF_Toc407713828\h21
HYPERLINK\l”_Toc407713829"参考文献PAGEREF_Toc407713829\h22

需求分析
Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
假若要在计算机上建立一个交通咨询系统则可以采用图的结构来表示实际的交通网络。这个资讯系统可以回答游客提出的各种问题。例如,一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线。假设图中每一站都需要换车，则这个问题反映到图上就是要找一条从顶点A到B所含边的数目最少的路径。我们只需从顶点A出发对图作广度优先搜索，一旦遇到顶点B就终止。由此所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径，路径上A与B之间的顶点就是途径中的中转站数。但是这只是一类最简单的图的最短路径的问题。有时对于旅客来说,可能更关心的是节省交通费用;对于司机来说里程和速度则是他们感兴趣的信息。为了在图上标示有关信息可对边赋以权的值，权的值表示两城市间的距离，或图中所需时间，或交通费用等等。此时路径长度的量度就不再是路径上边的数目,而是路径上边的权值之和.边赋以权值之后再结合最短路径算法来解决这些实际问题。Floyd算法是最短路径经典算法中形式较为简单，便于理解的一种。
算法基本原理
2。1邻接矩阵
邻接矩阵(AdjacencyMatrix）：是表示顶点之间相邻关系的矩阵。设G=(V，E）是一个图,其中V={v1,v2，…，vn}。G的邻接矩阵是一个具有下列性质的n阶方阵:
(1）对无向图而言,邻接矩阵一定是对称的，而且对角线一定为零（在此仅讨论