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

基于Floyd算法的最短路径问题的求解c++【实用文档】doc
文档可直接使用可编辑，欢迎下载

摘要

现实生活中许多实际问题的解决依赖于最短路径的应用，其中比较常用的是floyd算法。通过flｏｙd算法使最短路径问题变得简单化。采用图的邻接矩阵或邻接表实现最短路径问题中图的存储。采用Visual　Ｃ+＋6．０的控制台工程和MＦC工程分别实现基于floyd算法求最短路径的应用.
关键词:最短路径；ｆｌｏyd算法;邻接矩阵;ＭＦC工程
目录

1需求分析1
2算法基本原理1
2．1 邻接矩阵1
2。２ 弗洛伊德算法2
３类设计２
３。１　类的概述2
３．２　类的接口设计3
3.3 类的实现4
4基于控制台的应用程序7
4.1　主函数设计7
４。2 运行结果及分析8
５基于ＭFＣ的应用程序9
5．1 图形界面设计9
5.1　程序代码设计11
5.３ 运行结果及分析2０
结论21
参考文献2２

1 需求分析
Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法.该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
假若要在计算机上建立一个交通咨询系统则可以采用图的结构来表示实际的交通网络。这个资讯系统可以回答游客提出的各种问题。例如，一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线.假设图中每一站都需要换车，则这个问题反映到图上就是要找一条从顶点Ａ到B所含边的数目最少的路径。我们只需从顶点A出发对图作广度优先搜索，一旦遇到顶点Ｂ就终止。由此所得广度优先生成树上,从根顶点A到顶点B的路径就是中转次数最少的路径，路径上A与B之间的顶点就是途径中的中转站数.但是这只是一类最简单的图的最短路径的问题。有时对于旅客来说，可能更关心的是节省交通费用；对于司机来说里程和速度则是他们感兴趣的信息.为了在图上标示有关信息可对边赋以权的值，权的值表示两城市间的距离，或图中所需时间，或交通费用等等。此时路径长度的量度就不再是路径上边的数目,而是路径上边的权值之和.边赋以权值之后再结合最短路径算法来解决这些实际问题.Floyd算法是最短路径经典算法中形式较为简单，便于理解的一种。
2 算法基本原理
２．1　邻接矩阵
邻接矩阵（Ａdjaceｎcy Matrix）：是表示顶点之间相邻关系的矩阵.设G=（V,Ｅ）是一个图，其中Ｖ=｛v1,v２，…,vn}。G的邻接矩阵是一个具有下列性质的ｎ阶方阵:
（1)对无向图而言，邻接矩阵一定是对称的，而且对角线一定为零（在此仅讨论无向简单图)，有向图则不一定如此.
（2）在无向图中，任一顶点i的度为第i列所有元素的和，在有向图中顶点i的出度为第i行所有元素的和,而入度为第i列所有元素的和。
（3）用邻接矩阵法表示图共需要个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n／２个空间。
2．2 弗洛伊德算法
弗洛伊德算法使用图的邻接矩阵arcｓ[ｎ+1］［ｎ+１］来存储带权有向图.算法的基本思想是：设置一个ｎ x　n的矩阵A（k），其中除对角线的元素都等于0外,其它元素a(k)[i]［ｊ］表示顶点i到顶点j的路径长度,K表示运算步骤.开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为∞，当K＝０时， Ａ （0）［i][j］=aｒcｓ［i］［j］,以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为:
第一步,让所有边上加入中间顶点1，取A［i］[j]与A[ｉ］[1］＋A［１］[j］中较小的值作A[i］［j]的值，完成后得到A(1）；
第二步，让所有边上加入中间顶点２,取A[i][j］与A［i］［２］+A［2］[j]中较小的值,完成后得到A（2）…,如此进行下去，当第n步完成后，得到A（n），A(n）即为我们所求结果，A（n)[i]［j]表示顶点i到顶点j的最短距离。
因此弗洛伊德算法可以描述为：
Ａ（0）［i][j]＝arcｓ［i]［j]；　 　 　/／arcs为图的邻接矩阵
A（k）[i］［j］=miｎ｛Ａ（k－1) ［i]［j］，A（k—１）　[i][k］+Ａ（k－1） [k］［ｊ]｝，其中 ｋ=１，２，…，n（1)
定义一个n阶方阵序列:
D（—１)，Ｄ（0），…,Ｄ(n－1）.
Ｄ（—１）　[i][j］ = G。ａrcs［i］［ｊ］；
D（ｋ） ［i］［j] = min {　Ｄ（k-1)［i］[j]，D(k—1）［ｉ][k]　+　D(ｋ—1）[k]［j］　｝,k = ０,１，…，n-1（2）
其中Ｄ（0） ［i］[j］是从顶点vi 到vj中间顶点是v０的最短路径的长度;D(k） [ｉ]［j]是从顶点ｖi 到vj中间顶点的序号不大于k的最短路径长度；D（n-１）［ｉ］［j］是从顶点ｖi 到vj的最短路径长度。
3 类设计
3。1　类的概述
类代表了某一批对象的共性和特征。类是对象的抽象。类这种数据类型中的数据既包含数据也包含操作数据的函数。
声明类的一般形式:
ｃlass 类名
｛　privatｅ：
私有的数据和成员函数；
public:
公用的数据和成员函数;
　｝；
定义对象:类名对象名;
可以在类外定义成员函数,在函数名前加上类名，“：:”是作用域限定符或称作用域运算符用它说明函数式属于哪个类的。如下面程序中的
vｏidＭＧrａｐｈ：：ＣreateMGraｐh（MGraph ＆G)
｛
函数体
｝
３.2 类的接口设计
＃ｉｎｃludｅ<ioｓtream>
＃iｎclude 〈string〉
＃inｃlｕｄe <stdio.ｈ＞
uｓing　nａmespａｃe ｓtd；
＃defｉne　MａxVertexＮum 100
＃deｆiｎe INF 32767
ｃｌassMGraph
{prｉvａｔｅ:　　
ｃｈar ｖerteｘ［MaｘVｅrtexNum］;　 　 　 ／/顶点信息
inｔ eｄgｅs［MaxVｅｒtexNum］［MaxVｅrteｘNum］； //邻接矩阵
intn,ｅ；/／顶点数和边数
pubｌic:
　 　ｖoid　CｒeateMGrａｐh（MGrapｈ ＆)； 　 　 //构造有向图
ｖoidPpａｔh(int[]［100],int，ｉnt）；
　 voｉd Dispaｔh(ｉnt［］［１00]，ｉnt［][100]，ｉｎt）； //输出最短路径
void Fｌoyd(MGraph　G）； 　 　　　 　　／／Floyd算法的具体实现
｝;
首先将所需文件名写好，定义类MGrａph.在进行类体构造时将数据cｈar verｔex[MaxＶeｒtｅxNum］、ｉnt　eｄges[MaxＶerｔexNｕm］[MaxVｅｒtexNｕm]和inｔn,e定义为私有数据,将成员函数voiｄ　CｒeateMGｒａpｈ(MGraph ＆)、voiｄ Ppａth(ｉnt[]［100］，ｉnt,int）、void Dｉspａｔh(int［][10０］,iｎt[］[100］,inｔ)和void　Flｏyd（ＭGrａph　G)定义为公用的,以便非类体内的数据调用函数.
3。3　类的实现
vｏiｄ MＧｒaph:：ＣｒeateMＧraph(ＭGraph &G）//构造有向图
｛ 　
inｔi，ｊ，k,p； 　
cout<＜”请输入顶点数和边数：＂； 　
ｃin>〉G。n＞〉G。e； 　
couｔ＜〈"请输入顶点元素:"; 　
for （ｉ＝０；ｉ<G．n;i＋＋)　 　
｛　
ｃin＞＞G。ｖertex[i］； 　　
　 　　｝
for （ｉ=0;ｉ<Ｇ。n;i++) 　　
{ 　 　
foｒ (ｊ=0;j＜G．n;j+＋） 　
　 { 　
G。edges[ｉ］[j]=INF;　
if （ｉ＝=j）　　 　
　 　 　 { 　
G．edges[ｉ]［ｊ］=０；　
　 　　 }　　
｝
｝ 　 　
for （k=0;k〈G。e；k+＋）　　
　 { 　 　
coｕｔ<〈"请输入第"<〈k＋1〈〈＂条弧头弧尾序号和相应的权值：”； 　　
ciｎ＞＞i>>j〉〉p; 　
G。edges［i］［j]=ｐ;　 　
｝ 　
｝
vｏｉd MGraph：：Ｐpath(int ｐａｔh［][ＭaｘVerｔexNｕｍ]，iｎｔｉ，ｉnｔ j) //Ppath（）函数在pａｔｈ中递归输出从顶点vi到vj的最短路径.
{　　
inｔ k；　
　　 ｋ＝path［i］[j］；　
　 if （k=＝-１) // path[ｉ］［ｊ］＝ｉ时,顶点ｖi和vj之间无中间顶点,也就是说找到了始节点
　 ｛ 　
return;
}
Pｐath（pａｔｈ，i，k)； 　
ｐｒiｎtｆ（"％d"，k）；
Ppath（path,ｋ,j）；　
}　
vｏid　 ＭGｒaｐh：：Ｄｉspaｔh（int　A［］[MaxVertexＮum］，inｔ path[][ＭａｘVerｔexＮuｍ］，iｎt ｎ)／/输出最短路径的算法
｛　
ｉnｔi，ｊ; 　
for　（i=0；ｉ〈ｎ;i＋+）　　
　　｛ 　
for　(j＝0；j〈n;j++)　
　 {　
ｉf （A[ｉ］［j]==IＮF） 　
　 {
ｉf (ｉ!＝j)
　　 　 　　 ｛ 　
ｐrintf(＂从％d到%d没有路径\ｎ＂,i，ｊ)；
　　　 　 　　｝ 　
　 　 　　　}
else
　 ｛　
printf（”　 从％d到%d＝>路径长度：％d路径:"，i，j，A［i][j])；
prinｔf（＂%d，”，ｉ）；
Ｐpatｈ（ｐaｔh,i，j）；
printf（"%d\n＂，j）；
　　 　 }
　 　｝
　}
｝ 　

voｉdMGｒaｐh：：Floyd（MGｒaph G)
{ 　
ｉｎt A[MaｘVerｔexNｕm]［MaxVerｔexNum],ｐath［ＭaxＶerｔexＮuｍ］［MaxVertｅxNｕm]；
inti，j，k;　
fｏr （ｉ＝0；i＜Ｇ。n；i++)
　　　 {　
for　(j=０;j〈G．n；j++）
{
　 A[i]［j］＝G.ｅdｇes［ｉ］[j］；　
pａth［i］［j]=—1；
　　 }
　｝　　
fｏr （ｋ＝0；k＜G。n;k++） /／/向vi与vj之间中n次加入中间顶点
　｛ 　
ｆｏｒ （i=０；i<Ｇ．n；i++）
　　 　　 　｛
foｒ (j=0;j＜G．n；j＋+）
　　 　 　 　 { 　
if (A［i］［j]＞A[i][k］＋A[ｋ]［j]）
　 　 　 　 　 ｛　
　 　　　　　 　 　 A［i]［j］=A[i］[k］＋A［k]［j］；
　 　 ｐatｈ[ｉ]［j]=k；/／　表示从i节点到j节点，要经过k节点
　 　 　 　 }
　　　　 　　 　} 　
｝
　 　 ｝
Ｄispａｔh（A，patｈ，G。ｎ);
}
4 基于控制台的应用程序
4．1主函数设计
ｉnt main（）
{
MGｒapｈ G;
G.CreaｔeＭＧraph（G）;
G。Flｏyd(G）;
rｅturn 0；
}
在程序的主函数部分，定义一个MGraphａ类的对象G,调用成员函数CreateMGraｐh()和Flｏyd(）分别完成了采用图的邻接矩阵实现最短路径问题中图的存储和采用Flｏyd算法求每一对顶点的最短路径的任务。
4.2 运行结果及分析
将待测图的相关数据输入则得到如图1的运行结果。

图１ 程序运行结果
从图１可以看出:
整个程序中的矩阵存储采用的是一维数组和动态内存分配方式。
通过此类定义邻接矩阵,采用图的邻接矩阵实现最短路径问题中图的存储，然后通过主函数ｍaｉｎ调用class来实现，采用Floyd算法求每对顶点间最短路径从某个源点到其余各顶点的最短路径.
将图的基本信息输入，顶点数和边数４、8，顶点元素A、B、Ｃ、Ｄ,８条弧各自的序号和权值。运行程序得出每对顶点间的最短路径长度和路径.基于Fｌoyd算法成功的解决了最短路径问题.
5 基于MFC的应用程序
ＭＦC的图形界面程序与DOS界面程序的主要不同点是：ＭFＣ图形界面程序与ＤOS界面程序的输入输出方式不同，DOS界面程序采用字符交互式实现数据输入输出，主要通过cin,cout等Ｉ／Ｏ流实现，而MFC的图形程序界面采用标准Windows窗口和控件实现输入输出，因此必须在MFC类的框架下加入上面所设计的矩阵和方程组类,并通过图形界面的输入输出改造来完成。
5。1图形界面设计
首先在VＣ中建立MＦC ＡppWizａrd（exe)工程，名称为最短路径120３０60213，并在向导的Step1中选择Ｄiaｌoｇ　basｅｄ，即建立基于对话框的应用程序，如下图2～３所示。

图2建立MＦC ＡpｐWｉzａrｄ(eｘe）工程

图3 建立基于对话框的应用程序
将对话框资源中的默认对话框利用工具箱改造成如下界面，如图4所示。

图4表达式求值程序界面设计
在图4的设计过程中，选择文件按钮用于进行文件的选择,选择文件后顶点个数也随之显示；起点和终点编辑框分别用于输入起点终点信息；提交按钮用于输出最终结果。
5.1 程序代码设计
为了能够将对话框界面上的控件能够与代码联系起来，需要为5个Ｅdit Box控件建立Member Varｉaｂles，按Ｃtrl+ｗ键进入MFC CｌaｓｓWiｚａrd界面,选择Meｍｂｅr Variａblｅs选项卡，可显示成员变量设置界面，如图5所示.

图5成员变量设置界面
通过该界面设置与５个Edit Ｂｏx控件对应的成员变量,具体如表1所示。
表1 控件基本信息
控件ID
成员变量类型
成员变量名称
IＤC_ＥDIＴ_ＥND
ｉnｔ
m＿ｉntEnd
IDC_EDＩT_STＡＲＴ
ｉnt
m＿iｎtＳtart
IDＣ_EDＩT_RESULＴ
Ｃstriｎg
m＿intResｕl
IＤC_EＤIT_INFO
Cstring
m_sｔrＦileiｎfo
IDC＿EDＩT_ＮＵM
Int
ｍ_nNum
在MＦC中的主要代码:
(1).Ex＿FloｙdＤlg．cｐp中的代码为：
vｏid　CEx＿exＦloydDlg:：OｎButtonSｅｌ(） /／选择文件，并将文件中的数据保存到数组中
{
ﻩ// ＴODO: Adｄ yoｕr　coｎtroｌ notificａtｉon　handｌer　cｏｄe here
CFileＤialｏｇ　file(TRUE， NＵLL, NULL， NUＬL, _Ｔ（”(＊.txt）|*．txt|（*.doｃ）|＊.doc｜所有文件 （*.＊）|＊.＊| |"),NULL）;
／/*＊＊*＊***＊*＊＊**＊＊*＊*＊***＊＊*＊＊获得文件名＊＊***＊＊**＊＊**＊*****＊***＊//
ﻩ//CＳtrｉngｓtrＦileNａmｅ;
iｆ（fｉle。DoMｏdal（) == IDOＫ)
ﻩ｛
m_strＦilｅＩnfo = filｅ.GｅｔFileＮａme（）；
}
if(m＿strＦilｅInfｏ.IsEmｐty(）)
ﻩ｛
MesｓａgｅBox（”你还没有选择任何文件!”)；
ｒeturｎ；
｝
ｅｌse
ﻩ{
MessaｇeBox（＂你选择文件:＂+ m_ｓtrFileＩnfo+"请输入起点和终点”）；
GeｔDlgＩtem（IDＣ_EDＩT_STAＲT）-〉EｎableWinｄoｗ(ｔrue)；
ＧeｔDlgItｅm（IDC＿EＤIT＿END）—＞ＥnabｌeＷiｎdow(truｅ）;
GeｔDlgＩｔｅm(IDC_BUＴTON＿SUBMIT)—〉EｎａｂleＷinｄow(ｔrｕe）;
}
ﻩ／/将文件的数据读入到数组中
ＣStdｉｏＦileｆp；
if(!fp．Ｏpｅｎ(m＿stｒＦileInfｏ,CＦｉle：：ｍoｄeRead））
{ＭessaｇｅBｏx（"文件打开失败！”）；
return;
}
int ｉ=0；
CＳtringstr；
char* ｔemｐ；
BOOＬ ｂread　=　fp.ReaｄStrｉng(ｓtr);
ｔemp = str.ＧetBuｆfｅｒ(0)；
ﻩn=aｔoi（ｔｅmp）；
ｃoｕnts=n*n；
int ＊tp；　
tp＝new int[countｓ＋１］;
ｍ_nNUM=n；
c=nｅｗ int*[n+１］；
for（i=1； i＜=n; i++)
c[i］= ｎew int ［n+1］;
a=ｎｅw ｉｎｔ＊[ｎ＋１］;
ｆor（i=１； ｉ〈=ｎ； i＋+）
ａ[i］＝ nｅｗ int ［n＋1]；
ｒ=ｎeｗ int*［n+1]；
fｏr（ｉ=1; i<=n； ｉ++)
r［i］= nｅw inｔ ［n+1］;
bｒead = ｆp。ＲeａｄＳｔrinｇ(sｔr）；
ｉ＝0；
wｈilｅ（ｂreａd）
{temp ＝ str．ＧetBufｆer(０)；
tｐ［i++］ = atoi（ｔemp）；
ｂreａd =　ｆｐ。RｅadＳtriｎg（ｓtr）;
ﻩ}
ｆｐ.Close（)；
//将一维数组转化为二维数组放到数组c中
foｒ（i ＝ ０;　ｉ〈couｎts; ｉ+＋)
ﻩ{ｉf（ｔｐ[i］　！＝ －1）
ｃ[i/n+1］[i%n+1] =　ｔｐ[ｉ］；
else
c[ｉ/n+１］［ｉ%ｎ+1] ＝ mａｘiｎt;
}
UｐdateＤata（FＡLSＥ)；
｝
voidCEx_eｘFｌoydDｌg：:Ｅｘ_floyd（iｎtn，iｎt　*＊c，int **a，ｉｎｔ　＊＊r)
｛
iｎtｉ，ｊ,ｋ；
ｆor(i=1; i<=n; i+＋)
｛
fｏr(j=1； j<=n；　j++）
｛a[ｉ]［j]=c[i][j］;
r［i］[j］=0；
ﻩ}
｝
for（i＝1; i＜=n; i++）
for（j=１;　j＜＝ｎ； j++)
ﻩ{for(k=1；　ｋ〈=n; k＋+）
iｆ(ａ[i]［ｋ］＋ａ［k]［j]〈a［i]［j]）
ﻩ｛ａ［ｉ][j]＝a[i］［k］＋a［k］［ｊ];
r［i][j］=ｋ;
}
ﻩ｝
｝
intCEx_ｅxFloｙdDｌg：：Eｘ_ｏuｔput（iｎt ＊*r，inｔｉ,inｔ j）
｛int ｋ;
iｆ(r［i][j］！=0）
{
k=ｒ［i］[j];
Ｅｘ_ouｔｐut(r，i，k）；
strＲes．Formａt("%d—〉",ｋ）；
m_strRｅsult += strRｅs；
Ex_output(r，ｋ,j）；
}
return 0；
｝
ｖｏid CEｘ_exＦlｏｙｄＤｌg：:OnBｕttｏnSｕbｍiｔ(） ／/执行floyd算法计算最优值和最优解
｛／/ TODO：　Add ｙour ｃontrｏl notｉｆicatioｎ　handｌer code ｈere
UｐdateDaｔa(TRＵE）；　 //接受编辑框的数据
CＳｔringstrData； 　
Ex_floｙd（n,c，a,r）;
if(m＿intＳｔaｒt〉n||ｍ_intStarｔ＜1)
｛
ＭｅssaｇeＢox（"您输入的起点有误,请重新输入")；
}
if（m_intEnｄ＞ｎ||m_intEｎd＜１)
ﻩ{
ＭessａgeＢoｘ("您输入的终点有误，请重新输入"）；
}
strData。Foｒmａｔ（"起点为：%ｄ”,m_intSｔａrt）；
ｍ_sｔｒRｅsult +＝　sｔｒData + ”\r\n” ;
stｒＤａta.Forｍat（"终点为：%d＂,m_intEnd)；
m_strResult　+= strData + ”\ｒ\n”；
strＤatａ.Formａt（"最优值：")
ｓhortesｔ[％d]［％d］=％ｄ\n＂,m_intStart,m_iｎtEｎｄ，a［m_intStaｒt]［m＿intEnd］);
m＿sｔrResulｔ += sｔrData　+ "\r\ｎ”;
ｓtrRes。Ｆorｍaｔ（”最佳路径:％d—>＂,m_inｔStart);
m_strＲesｕlt　+= sｔrRes；
Ex_ｏuｔput（r，m_ｉｎtStａrt，m_intＥnｄ)；
ｓtrReｓ。Formａt（"％d”，ｍ_inｔEnd);
m＿stｒResｕlt += sｔrRes;
UpdateＤａta(FALＳE)； 　 //更新编辑框的数据
}
（2）Ex_FｌoyｄDlg．h中的主要代码为：
cｌasｓCEｘ_exFlｏydＤlg　: publiｃ CDialoｇ
{
/／　Coｎstｒuction
public：
CEx_exFloydDlg(CWnｄ＊ pPaｒent　= NＵLL)；ﻩ// sｔａｎdard construｃｔor
voiｄEx_floyd (inｔn，iｎｔ ＊＊c，int ＊＊a，ｉnt　＊*ｒ）;
intEx＿oｕtｐuｔ（int ＊＊r,ｉnti，int ｊ）;　
/／ Dｉalｏg Datａ
//{{ＡFX_ＤＡTA(CEx_exＦｌoydDlg)
enｕm ｛ IDD = IDD_EX＿EXFLOＹＤ_ＤＩAＬOG };
CＳｔrｉnｇm＿ｓｔrＦilｅInfo；
ｉntｍ＿intEnd;
intｍ＿intＳｔart；
CＳtringm_sｔrReｓulｔ；
intm_ｎNUM;
protecteｄ:
ﻩＨICOＮ m_ｈIcoｎ；
ｉnt n　; //图形中顶点的个数
inｔ　**a; //最优值矩阵
inｔ　*＊c;/／顶点之间的距离矩阵
iｎt *＊r；／/路由矩阵
iｎt couｎtｓ；
ｉｎｔ　＊tp；
CＳtringｓｔrRes；
／／ Geｎeratｅd meｓsａge　ｍａp ｆuｎcｔioｎs
/／｛{AFX_MSＧ（CEx＿exＦlｏydDｌg）
virtual　ＢOOL　ＯｎIｎitDialｏg(）;
ａfx_ｍｓg　ｖoid ＯｎSysCommaｎd（ＵINT nID,　ＬPARAM　lＰaram)；
ａfx_mｓg ｖｏid OnPaint（);
aｆx_ｍsｇ　HCURSＯR　OｎＱuerｙDｒagIｃon()；
aｆｘ＿ｍｓg　ｖoid OnButtonＳel(）;
ａfx_msｇ void OnＢuttｏnSubｍit（）;
｝
(3)两个外部调用函数模块：
ｖoidＣEx_exFｌoydDｌｇ::Eｘ＿floｙｄ（ｉntn,ｉnt ＊＊c，inｔ **a，int ＊＊ｒ）
｛iｎｔi,j，k;
for(i=1; i<=n；　i+＋）
ﻩ｛
fｏｒ（j=1； j〈＝n;　j++）
ﻩ{a［i］[j]=ｃ[i]［ｊ]；
r［i］[j］＝0；
ﻩ}
｝
for(i=１; ｉ＜=n； ｉ+＋）
ｆoｒ(ｊ=１; j<＝ｎ; ｊ＋＋）
ﻩ｛fｏｒ(k=1; k<=n；　k++）
if（a［i]［k］＋a［k］［j]<a［ｉ]［j］）
{a［i］［j]=a[ｉ]［k］+ａ[k]［ｊ];
r[ｉ］［ｊ］=k;
ﻩ｝
ﻩ｝
｝
inｔCEx_ｅｘFloｙdDlg：:Ｅx_output（int *＊r，intｉ，int ｊ）
｛iｎｔ k；
if(ｒ［i][j］！＝0)
ﻩ｛
ﻩk=r[i］[ｊ］;
Ex＿ouｔput(r,i,k);
stｒRｅｓ。Format(＂％d-〉”，k)；
m_ｓｔｒRｅｓｕlｔ += sｔrＲes;
Ex_outｐｕt(r,k，j);
ﻩ｝
ｒｅturｎ　０；
｝

if（fｉle．DoMｏdaｌ（)　==　IDＯＫ)
ﻩ｛
m_ｓtｒＦiｌeInｆｏ　= fｉlｅ.ＧetFileＮaｍe()；
ﻩ}
if（ｍ_sｔrFiｌeInfｏ。IsEmptｙ（）)
ﻩ｛
MｅssageBｏx（＂你还没有选择任何文件！”）;
return;
ﻩ}
else
ﻩ｛MessaｇeＢox（"你选择文件:”+ ｍ＿strFileIｎfo+”请输入起点和终点"）；
ＧetDlgＩｔｅm（IDC_ＥDIT＿START）-＞EnableWiｎdｏｗ(trｕe);
GetDlgItem（IDC＿EDIT_END)－＞EnablｅWiｎdow（ｔrｕe）；
GｅtＤlｇIｔem(IDC_BUＴＴON＿SUBＭIT)->EｎａbleWiｎdow（ｔrue)；
ﻩ｝//将文件的数据读入到数组中
CStdiｏFiｌｅfp;
if（！fp．Open（m_stｒＦｉlｅInfo,ＣFiｌｅ：:moｄeＲeaｄ))
ﻩ{MessageBｏx（"文件打开失败！")；
rｅturn；
ﻩ｝
iｎt i=0；
ＣStringstr;
char＊　temp；
ＢOＯL　breａｄ = fｐ．ReaｄＳtring(sｔｒ）;
temp　=　ｓtr。GeｔBufｆｅr(0)；
n=ａtoｉ（teｍp）;
couｎｔs＝n＊n;
iｎｔ ＊tp；　
tp=ｎｅｗ　ｉnt［counts＋1］；
m_ｎNＵM=n;
c=nｅw int*[ｎ+1]；
for(i＝１； i〈=n；　ｉ++）
ｃ[ｉ]＝ new　int ［n+1］；
a=ｎeｗ iｎt*[n+1］；
fｏr（i=１; i〈=n； ｉ++)
a[i］= new int ［n+１］；
r＝new　int*[n+1]；
for(i＝１; ｉ〈=n; i++)
ｒ[i]= ｎｅw iｎt [n+1]；
ｂｒeaｄ　=　fp．ＲeadSｔring（str);
ﻩi=0;
while（bｒead）
｛ｔeｍp =　ｓtr．GetBufｆer（０）；
tp[ｉ+＋］ = ａtｏi(temp）;
bread ＝ fp．RｅadSｔring(str);
｝
fp．Cloｓe（)；/／将一维数组转化为二维数组放到数组ｃ中
fｏｒ（i = 0; ｉ＜countｓ； i++)
｛if（tp[i] !＝ －1)
c［i/ｎ+１］［i％n+１］　＝ ｔp[i］；
ｅｌse
ｃ[i／n+1]［i％n+１]　＝　ｍａxｉｎt；
ﻩ}
UpｄａteDatａ（FＡＬSE）；
｝
5．３ 运行结果及分析
先选择“选择文件按钮”，在其中选择一个文件后如1．txt。会在顶点个数只读编辑框中显示出你所选文件中的顶点个数,分别在起点和终点编辑框中输入起点和终点，在点击提交，会出现如图５运行界面。
图5单击提交按钮后的界面
在图5中可以看出：
进行操作时，单击选择文件框,选择所需要的文档,该文档存储了待测图的全部信息,随即生成顶点个数。将你所要测的最短路径的一对顶点的起点和终点输入相应位置.待测信息输入完毕后，单击提交按钮,所测一对顶点的求出过程都会显示在结果对应的显示框中。成功的在MFC中实现了基于Flｏｙd算法求每对顶点间的最短路径问题。
MＦＣ显示的界面，更清晰直观的反映出所要求解的最短路径问题，便于用户的理解和操作.

结论
本次课程设计主要研究基于Fｌoyd算法的最短路径问题的求解。论文主体大致分为五个部分，第一部分介绍了Fｌoyｄ算法的需求分析;第二部分介绍了算法的基本原理;第三部分主要是类设计,介绍了类、类的接口设计和类的实现；第四部分是基于控制台的应用程序;第五部分是基于MFC的应用程序。完整的叙述了所研究的问题。
编写程序过程中,首先需要了解邻接矩阵的概念,才能采用图的邻接矩阵实现最短路径问题中图的储存,然后才能采用Flｏyd算法求每一对顶点的最短路径.
实验过程中用两种方式来实现基于Fｌoyd算法的最短路径问题求解：一种是Win32 Ｃonsolｅ Applicａtion,输入输出采用传统ＤOS的字符式交互界面;另一种是MFC ApｐＷｉｚarｄ(exe），输入输出采用基于Windoｗｓ的图形式交互界面。编写DOＳ相关算法时采用类与对象进行编程，定义类MＧrａｐｈ，包含的数据元素有顶点信息、邻接矩阵和顶点数和边数，还包括成员函数ｖoid ＣreatｅMGraph（MGrａph ＆）；用于构造有向图、voｉd Ppath（int[][1０0］，ｉｎt,int）;、ｖｏｉd Dｉspatｈ（int［][１00]，inｔ［］[１00],ｉｎt）;实现输出最短路径、void Floyd(MＧｒａph G）;则是Floyd算法的具体实现。通过定义对象对成员函数进行调用,完成基于floyd算法求最短路径问题。MFC虽然算法复杂，但是基于MFC的应用程序能更形象直接的供用户使用。
最后要感谢老师和同学的帮助，我才能成功的完成这次课程设计的论文。这次课程设计作为学完面向对象程序设计课程后的一次全面的综合练习。通过这次设计增加我对面向对象程序设计的基础理论的理解，掌握面向对象程序设计开发的基本方法,进一步提高了综合运用所学知识的能力。

参考文献
［1]　谭浩强。C+＋基础入门大全．北京：清华大学出版社,20１2：1０0—1０2
［２］　郑莉，董渊,张瑞丰。Ｃ++语言程序设计（第3版).北京：清华大学出版社，2０07：25-60
[3]　钱能。C＋＋程序设计教程(第２版）．北京:清华大学出版社，2０07:１00-1３０
［４］ 欧阳志宏,董霖，钟俊华。MＦC程序设计轻松入门．北京：人民邮电出版社,２０0９
[５］严蔚敏，吴伟民．数据结构（C语言版)．北京：清华大学出版社,２007:168-192

专业综合设计报告

课程名称：电子专业综合设计
　 设计名称: 基于模拟退火算法的ＴSP算法
姓名:
学号:　
班级：电子09０3
指导教师：朱正为
　 　 　起止日期：201２。11．1—201２.12．3０

专业综合设计任务书
学生班级:电子0９03 　 学生姓名：学号： 　2０09５830 　 　 　
设计名称:基于模拟退火算法的ＴSP算法 　 　 　 　 　 　 　 　
起止日期：2012.11．1—2012。1２.３0指导教师

设计要求:
旅行商问题，即TＳP问题（Traveｌling Ｓａlｅsmａn Proｂlem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。　 　
　 　此设计是用模拟退火算法来实现ＴＳP问题的寻求最优解。

专业综合设计学生日志

时间
设计内容
2012．11。９
初步了解模拟退火算法的TＳP算法
201２．1１。12
设计算法流程、确定解题思路
20１2。1１.2０
讨论算法流程及解题思路的可行性，为仿真做准备
20１2.１2。２
运用MATLＡＢ软件进行实验仿真,分析仿真结果
2012.12。8
整理实验报告
2012．12.17
答辩

专业综合设计考勤表

周
星期一
星期二
星期三
星期四
星期五

专业综合设计评语表

指导教师评语:

成绩：指导教师：

年月日

一　设计目的和意义5
二设计原理5
2。１ 模拟退火算法的基本原理.。。。。。..。。．。。.。。.。．.．.．．．.。．。．..。.．。...。．.．。。．。。..．.。.。。．。。．.．.．。.。.。.。．..．。...．.。。..。。..。。..。．.．。.。。.．．。...。。.5
2。2 TSＰ问题介绍.。。。。..．.．。。。.。。。..。．。。..。．....．．..。。．.．。。.．。。.。。．.．.。.．。.．.。.。．...．．。．.．．。．。.。。.。.。．。．..．．。．．.。..。。．．...．.。．.。.。。。...．。。．。。..。。。６
三详细设计步骤..．．......。。.。。.。。．..．..．。。。..．。。..．．。.。．.．...。.。.。.．.．.。...．。...．．..．..。。.。．。.．..．。..。。。．。。。。..。.。...．.。。。。.．．..。。.。.。．.．.．。.。。。.。.．..．．.。．7
3.1.算法流程8
3.2模拟退火算法实现步骤８
四设计结果及分析9
4．1 MAＴＬAB程序实现及主函数．.．．。.。。。．.。.．。．。.。．。.．。．..。.．.。。。.．..．.。。.．。。.．．．。。.．．．.。．．．。.。。．。.．。．...。...．。。.。.。.。．．。..．．．．.。。。..。.。．．．.9
4.1。1 计算距离矩阵。．．。．.。.．。。.。。。..。．。。。。。..．。..．。.。。.。..。。.。。.。。..。..。...。。。。。。.。.。。。．。。...．。.。..。。...。．。.。．．．.。.．。．..．。．．...．。．。９
　　　　 　　4.1。2 初始解..。。。。．．.。.。.．．.。．．。．.。.。．。．..。．．。.。。。.。..。。。．。。..。.．.。.。。。．.。．．．..。．。．。。.。．......．.。．.。..。.．.。。..。..。.．。。。.。.．．．.．。。.。。．.１0
　 　 ４.1.3 生成新解.．...。．。..。。