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

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

摘要
现实生活中许多实际问题的解决依赖于最短路径的应用，其中比较常用的是floyd算法。通过floyd算法使最短路径问题变得简单化.采用图的邻接矩阵或邻接表实现最短路径问题中图的存储。采用Visual C++6。0的控制台工程和MFC工程分别实现基于floyd算法求最短路径的应用。
关键词:最短路径;floyd算法；邻接矩阵；MFC工程
目录
1需求分析1
2算法基本原理1
2。1 邻接矩阵1
2.2 弗洛伊德算法2
3类设计2
3.1 类的概述2
3。2 类的接口设计3
3.3 类的实现4
4基于控制台的应用程序7
4.1 主函数设计7
4。2 运行结果及分析8
5基于MFC的应用程序9
5.1 图形界面设计9
5.1 程序代码设计11
5。3 运行结果及分析20
结论21
参考文献22
II

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）对无向图而言,邻接矩阵一定是对称的，而且对角线一定为零（在此仅讨论无向简单图）,有向图则不一定如此。
（2)在无向图中,任一顶点i的度为第i列所有元素的和,在有向图中顶点i的出度为第i行所有元素的和,而入度为第i列所有元素的和.
（3）用邻接矩阵法表示图共需要个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n/2个空间。
2.2 弗洛伊德算法
弗洛伊德算法使用图的邻接矩阵arcs［n+1][n+1]来存储带权有向图.算法的基本思想是:设置一个n x n的矩阵A（k），其中除对角线的元素都等于0外，其它元素a（k）［i］[j］表示顶点i到顶点j的路径长度，K表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路径长度,没有有向边时，路径长度为∞,当K=0时, A (0)[i]［j］=arcs［i］［j］，以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为:
第一步，让所有边上加入中间顶点1，取A［i][j］与A[i][1]+A[1][j]中较小的值作A[i］［j]的值，完成后得到A（1);
第二步，让所有边上加入中间顶点2，取A［i］［j］与A［i]［2］+A[2][j]中较小的值,完成后得到A（2)…，如此进行下去，当第n步完成后，得到A(n），A(n）即为我们所求结果,A(n）[i］［j]表示顶点i到顶点j的最短距离。
因此弗洛伊德算法可以描述为：
A（0）[i]［j］=arcs［i][j]； //arcs为图的邻接矩阵
A（k）[i］［j］=min｛A（k—1） ［i][j］,A(k-1） [i］[k］+A（k—1) [k］[j］},其中 k=1，2，…,n(1）
定义一个n阶方阵序列：
D（—1），D(0），…,D（n—1）.
D（—1） ［i］[j] = G。arcs［i]［j];
D(k) [i］［j] = min { D（k-1）[i］［j]，D（k-1）［i][k］ + D(k—1）[k］［j] ｝，k = 0，1,…,n—1(2)
其中D（0) ［i]［j]是从顶点vi 到vj中间顶点是v0的最短路径的长度;D（k) ［i]［j]是从顶点vi 到vj中间顶点的序号不大于k的最短路径长度;D（n-1）［i］［j］是从顶点vi 到vj的最短路径长度。
3 类设计
3.1 类的概述
类代表了某一批对象的共性和特征.类是对象的抽象.类这种数据类型中的数据既包含数据也包含操作数据的函数。
声明类的一般形式：
class 类名
｛ private：
私有的数据和成员函数;
public:
公用的数据和成员函数；
｝；
定义对象：类名对象名；
可以在类外定义成员函数，在函数名前加上类名，“:："是作用域限定符或称作用域运算符用它说明函数式属于哪个类的。如下面程序中的
voidMGraph：：CreateMGraph（MGraph &G）
｛
函数体
}
3。2 类的接口设计
#include〈iostream〉
＃include 〈string〉
#include <stdio.h>
using namespace std；
＃define MaxVertexNum 100
#define INF 32767
classMGraph
｛private：
char vertex［MaxVertexNum］； //顶点信息
int edges[MaxVertexNum][MaxVertexNum］； //邻接矩阵
intn，e；//顶点数和边数
public：
void CreateMGraph（MGraph ＆）; //构造有向图
voidPpath(int［］[100],int，int）;
void Dispath（int［］[100],int［］［100］,int）; //输出最短路径
void Floyd（MGraph G）; //Floyd算法的具体实现
｝;
首先将所需文件名写好，定义类MGraph。在进行类体构造时将数据char vertex［MaxVertexNum］、int edges[MaxVertexNum］［MaxVertexNum］和intn,e定义为私有数据，将成员函数void CreateMGraph（MGraph ＆）、void Ppath（int[][100］,int,int)、void Dispath（int［］[100］，int［］［100］，int)和void Floyd(MGraph G)定义为公用的，以便非类体内的数据调用函数。
3。3 类的实现
void MGraph::CreateMGraph（MGraph &G）//构造有向图
｛
inti，j,k,p;
cout〈〈"请输入顶点数和边数：";
cin>〉G。n>〉G。e；
cout<<”请输入顶点元素："；
for （i=0；i〈G.n；i++)
｛
cin>〉G。vertex［i];
｝
for (i=0；i〈G。n；i++）
{
for (j=0;j<G。n；j++)
｛
G.edges［i][j]=INF；
if (i==j）
{
G.edges［i]［j］=0；
}
}
｝
for （k=0；k〈G。e；k++)
｛
cout〈〈”请输入第”<〈k+1<<”条弧头弧尾序号和相应的权值:"；
cin〉>i〉〉j〉〉p;
G。edges[i］[j］=p；
｝
｝
void MGraph：：Ppath（int path［]［MaxVertexNum]，inti，int j） //Ppath(）函数在path中递归输出从顶点vi到vj的最短路径。
{
int k；
k=path［i］[j]；
if (k==—1） // path［i］［j］=i时,顶点vi和vj之间无中间顶点,也就是说找到了始节点
｛
return;
}
Ppath（path,i，k)；
printf（”%d”,k）；
Ppath(path，k，j）;
}
void MGraph：：Dispath（int A[]［MaxVertexNum］，int path［］[MaxVertexNum］,int n)//输出最短路径的算法
｛
inti，j；
for (i=0；i〈n;i++)
｛
for (j=0;j〈n；j++）
{
if （A［i]［j］==INF)
｛
if (i!=j)
{
printf(”从％d到%d没有路径\n”，i,j)；
}
｝
else
｛
printf(" 从％d到%d=>路径长度:％d路径：”，i，j,A[i］［j］);
printf("%d，”,i）；
Ppath（path,i，j）；
printf（”％d\n”,j);
｝
｝
｝
｝
voidMGraph：:Floyd（MGraph G）
{
int A[MaxVertexNum］［MaxVertexNum]，path［MaxVertexNum]［MaxVertexNum］；
inti，j,k；
for （i=0;i<G.n；i++）
{
for （j=0；j〈G。n;j++）
｛
A［i]［j］=G。edges[i］［j］;
path[i］［j］=—1;
}
｝
for (k=0;k〈G。n；k++） ///向vi与vj之间中n次加入中间顶点
｛
for （i=0;i〈G.n;i++）
｛
for （j=0；j〈G。n;j++)
{
if （A［i］[j］>A[i][k]+A[k］[j]）
{
A[i］[j］=A[i][k］+A[k]［j］；
path[i］[j]=k；// 表示从i节点到j节点，要经过k节点
｝
｝
}
}
Dispath（A，path，G。n）；
｝
4 基于控制台的应用程序
4。1主函数设计
int main（）
{
MGraph G;
G。CreateMGraph（G）;
G。Floyd（G）;
return 0；
}
在程序的主函数部分，定义一个MGrapha类的对象G，调用成员函数CreateMGraph（）和Floyd（）分别完成了采用图的邻接矩阵实现最短路径问题中图的存储和采用Floyd算法求每一对顶点的最短路径的任务.
4。2 运行结果及分析
将待测图的相关数据输入则得到如图1的运行结果.
图1 程序运行结果
从图1可以看出：
整个程序中的矩阵存储采用的是一维数组和动态内存分配方式.
通过此类定义邻接矩阵，采用图的邻接矩阵实现最短路径问题中图的存储，然后通过主函数main调用class来实现,采用Floyd算法求每对顶点间最短路径从某个源点到其余各顶点的最短路径。
将图的基本信息输入，顶点数和边数4、8,顶点元素A、B、C、D,8条弧各自的序号和权值.运行程序得出每对顶点间的最短路径长度和路径。基于Floyd算法成功的解决了最短路径问题。
5 基于MFC的应用程序
MFC的图形界面程序与DOS界面程序的主要不同点是：MFC图形界面程序与DOS界面程序的输入输出方式不同，DOS界面程序采用字符交互式实现数据输入输出，主要通过cin，cout等I/O流实现，而MFC的图形程序界面采用标准Windows窗口和控件实现输入输出,因此必须在MFC类的框架下加入上面所设计的矩阵和方程组类,并通过图形界面的输入输出改造来完成。
5。1图形界面设计
首先在VC中建立MFC AppWizard(exe）工程，名称为最短路径1203060213,并在向导的Step1中选择Dialog based，即建立基于对话框的应用程序，如下图2～3所示.
图2建立MFC AppWizard(exe）工程
图3 建立基于对话框的应用程序
将对话框资源中的默认对话框利用工具箱改造成如下界面，如图4所示。
图4表达式求值程序界面设计
在图4的设计过程中，选择文件按钮用于进行文件的选择，选择文件后顶点个数也随之显示;起点和终点编辑框分别用于输入起点终点信息；提交按钮用于输出最终结果。
5。1 程序代码设计
为了能够将对话框界面上的控件能够与代码联系起来，需要为5个Edit Box控件建立Member Variables，按Ctrl+w键进入MFC ClassWizard界面，选择Member Variables选项卡，可显示成员变量设置界面，如图5所示。
图5成员变量设置界面
通过该界面设置与5个Edit Box控件对应的成员变量，具体如表1所示。
表1 控件基本信息
控件ID
成员变量类型
成员变量名称
IDC_EDIT_END
int
m_intEnd
IDC_EDIT_START
int
m_intStart
IDC_EDIT_RESULT
Cstring
m_intResul
IDC_EDIT_INFO
Cstring
m_strFileinfo
IDC_EDIT_NUM
Int
m_nNum
在MFC中的主要代码:
(1）。Ex_FloydDlg。cpp中的代码为：
void CEx_exFloydDlg::OnButtonSel(） //选择文件，并将文件中的数据保存到数组中
｛
// TODO： Add your control notification handler code here
CFileDialog file（TRUE， NULL， NULL， NULL, _T（"(*.txt）｜＊。txt｜(*.doc）｜*.doc｜所有文件 （＊.*）|＊。*｜ ｜"），NULL);
//＊＊＊**＊＊*＊**＊＊＊＊**＊＊＊＊***＊*＊*获得文件名＊*＊＊＊＊＊＊＊＊＊**＊*＊＊＊＊*＊＊*＊//
//CStringstrFileName；
if(file.DoModal(） == IDOK)
｛
m_strFileInfo = file。GetFileName（)；
｝
if（m_strFileInfo。IsEmpty())
｛
MessageBox（"你还没有选择任何文件！”）；
return；
｝
else
{
MessageBox（"你选择文件："+ m_strFileInfo+"请输入起点和终点"）；
GetDlgItem(IDC_EDIT_START）—〉EnableWindow（true)；
GetDlgItem（IDC_EDIT_END)—〉EnableWindow(true);
GetDlgItem（IDC_BUTTON_SUBMIT）—〉EnableWindow（true)；
}
//将文件的数据读入到数组中
CStdioFilefp;
if（！fp。Open(m_strFileInfo，CFile:：modeRead））
{MessageBox("文件打开失败！”）；
return；
｝
int i=0;
CStringstr；
char＊ temp;
BOOL bread = fp。ReadString（str）;
temp = str。GetBuffer(0)；
n=atoi（temp）；
counts=n＊n;
int ＊tp;
tp=new int［counts+1］;
m_nNUM=n;
c=new int＊[n+1］;
for(i=1; i<=n； i++）
c［i]= new int ［n+1]；
a=new int*[n+1]；
for（i=1； i〈=n； i++）
a［i］= new int ［n+1];
r=new int*［n+1]；
for（i=1； i〈=n； i++）
r［i］= new int [n+1]；
bread = fp.ReadString(str）；
i=0;
while（bread)
｛temp = str。GetBuffer（0）；
tp［i++] = atoi（temp）；
bread = fp.ReadString（str）;
｝
fp。Close（）；
//将一维数组转化为二维数组放到数组c中
for（i = 0; i〈counts； i++）
{if（tp［i] ！= —1）
c[i/n+1][i％n+1] = tp［i］；
else
c［i/n+1]［i％n+1］ = maxint;
｝
UpdateData(FALSE）；
｝
voidCEx_exFloydDlg：:Ex_floyd(intn，int ＊＊c,int *＊a,int ＊*r）
{
inti,j,k；
for（i=1； i〈=n; i++)
{
for（j=1； j<=n; j++）
{a[i］［j］=c[i][j］；
r[i]［j］=0;
｝
}
for(i=1； i<=n； i++）
for（j=1； j<=n； j++）
｛for（k=1； k〈=n； k++）
if（a［i]［k］+a[k］［j］<a［i]［j]）
｛a［i］[j］=a[i］［k]+a[k］[j］；
r[i]［j]=k;
}
｝
｝
intCEx_exFloydDlg::Ex_output（int **r，inti，int j）
{int k；
if（r［i］［j]!=0）
｛
k=r［i][j］；
Ex_output（r,i，k）;
strRes。Format（"％d-〉",k)；
m_strResult += strRes；
Ex_output(r，k，j)；
}
return 0;
}
void CEx_exFloydDlg::OnButtonSubmit() //执行floyd算法计算最优值和最优解
｛// TODO： Add your control notification handler code here
UpdateData(TRUE)； //接受编辑框的数据
CStringstrData；
Ex_floyd(n,c，a，r)；
if(m_intStart〉n｜｜m_intStart<1）
｛
MessageBox(”您输入的起点有误,请重新输入")；
｝
if(m_intEnd>n｜｜m_intEnd<1）
{
MessageBox(”您输入的终点有误，请重新输入”）；
｝
strData.Format（”起点为：％d”,m_intStart)；
m_strResult += strData + ”\r\n" ;
strData。Format("终点为：％d"，m_intEnd)；
m_strResult += strData + ”\r\n”;
strData。Format（”最优值:"）
shortest［％d］［％d]=％d\n”,m_intStart，m_intEnd,a［m_intStart］［m_intEnd］）；
m_strResult += strData + ”\r\n”；
strRes。Format(”最佳路径：%d—〉",m_intStart)；
m_strResult += strRes；
Ex_output（r，m_intStart，m_intEnd)；
strRes.Format（"％d",m_intEnd)；
m_strResult += strRes；
UpdateData(FALSE)； //更新编辑框的数据
｝
（2）Ex_FloydDlg。h中的主要代码为：
classCEx_exFloydDlg : public CDialog
｛
// Construction
public：
CEx_exFloydDlg（CWnd＊ pParent = NULL）； // standard constructor
voidEx_floyd (intn，int ＊*c,int ＊＊a，int ＊＊r)；
intEx_output（int ＊＊r，inti，int j）；
// Dialog Data
//｛{AFX_DATA（CEx_exFloydDlg）
enum { IDD = IDD_EX_EXFLOYD_DIALOG };
CStringm_strFileInfo；
intm_intEnd；
intm_intStart;
CStringm_strResult;
intm_nNUM；
protected：
HICON m_hIcon;
int n ； //图形中顶点的个数
int *＊a； //最优值矩阵
int ＊＊c；//顶点之间的距离矩阵
int **r；//路由矩阵
int counts；
int *tp；
CStringstrRes；
// Generated message map functions
//｛｛AFX_MSG（CEx_exFloydDlg)
virtual BOOL OnInitDialog（)；
afx_msg void OnSysCommand（UINT nID， LPARAM lParam）;
afx_msg void OnPaint（）；
afx_msg HCURSOR OnQueryDragIcon（）；
afx_msg void OnButtonSel（）；
afx_msg void OnButtonSubmit(）；
}
（3)两个外部调用函数模块：
voidCEx_exFloydDlg:：Ex_floyd（intn,int ＊＊c，int ＊*a,int ＊＊r)
｛inti，j，k；
for(i=1; i〈=n； i++)
{
for(j=1; j<=n； j++）
｛a［i][j］=c［i][j]；
r［i][j］=0；
｝
｝
for(i=1; i<=n； i++)
for（j=1; j<=n; j++）
{for（k=1； k<=n； k++）
if(a［i]［k］+a［k］[j］〈a［i]［j］）
｛a[i][j]=a［i]［k］+a［k][j］；
r［i］［j]=k；
｝
｝
｝
intCEx_exFloydDlg：：Ex_output（int ＊＊r,inti，int j）
｛int k;
if(r［i][j］！=0)
｛
k=r［i］［j］；
Ex_output(r,i，k）;
strRes。Format（”%d->"，k)；
m_strResult += strRes;
Ex_output（r,k，j)；
}
return 0；
}
if（file。DoModal（） == IDOK）
｛
m_strFileInfo = file.GetFileName（）；
｝
if(m_strFileInfo。IsEmpty())
{
MessageBox("你还没有选择任何文件！”);
return;
｝
else
{MessageBox（”你选择文件：”+ m_strFileInfo+”请输入起点和终点”);
GetDlgItem（IDC_EDIT_START)—>EnableWindow（true);
GetDlgItem(IDC_EDIT_END）—〉EnableWindow（true）；
GetDlgItem（IDC_BUTTON_SUBMIT）—〉EnableWindow（true);
}//将文件的数据读入到数组中
CStdioFilefp；
if（！fp。Open（m_strFileInfo,CFile::modeRead）)
｛MessageBox("文件打开失败!”);
return；
｝
int i=0；
CStringstr;
char* temp;
BOOL bread = fp。ReadString（str）;
temp = str。GetBuffer（0）;
n=atoi(temp）；
counts=n＊n；
int ＊tp；
tp=new int［counts+1］；
m_nNUM=n；
c=new int＊［n+1]；
for（i=1； i<=n； i++）
c[i]= new int [n+1］;
a=new int*[n+1];
for（i=1； i<=n; i++)
a［i］= new int ［n+1];
r=new int＊［n+1］；
for（i=1; i<=n; i++)
r［i]= new int [n+1］；
bread = fp。ReadString（str)；
i=0;
while（bread)
｛temp = str.GetBuffer（0);
tp[i++] = atoi（temp）;
bread = fp.ReadString（str）;
}
fp.Close(）；//将一维数组转化为二维数组放到数组c中
for（i = 0； i〈counts； i++）
｛if（tp［i] != —1）
c［i/n+1］［i%n+1］ = tp［i］;
else
c[i/n+1][i%n+1］ = maxint;
｝
UpdateData（FALSE）;
｝
5。3 运行结果及分析
先选择“选择文件按钮”，在其中选择一个文件后如1.txt.会在顶点个数只读编辑框中显示出你所选文件中的顶点个数，分别在起点和终点编辑框中输入起点和终点，在点击提交，会出现如图5运行界面。
图5单击提交按钮后的界面
在图5中可以看出：
进行操作时，单击选择文件框,选择所需要的文档，该文档存储了待测图的全部信息，随即生成顶点个数.将你所要测的最短路径的一对顶点的起点和终点输入相应位置。待测信息输入完毕后，单击提交按钮，所测一对顶点的求出过程都会显示在结果对应的显示框中。成功的在MFC中实现了基于Floyd算法求每对顶点间的最短路径问题。
MFC显示的界面,更清晰直观的反映出所要求解的最短路径问题，便于用户的理解和操作.
结论
本次课程设计主要研究基于Floyd算法的最短路径问题的求解。论文主体大致分为五个部分,第一部分介绍了Floyd算法的需求分析;第二部分介绍了算法的基本原理；第三部分主要是类设计，介绍了类、类的接口设计和类的实现；第四部分是基于控制台的应用程序；第五部分是基于MFC的应用程序。完整的叙述了所研究的问题。
编写程序过程中,首先需要了解邻接矩阵的概念，才能采用图的邻接矩阵实现最短路径问题中图的储存,然后才能采用Floyd算法求每一对顶点的最短路径。
实验过程中用两种方式来实现基于Floyd算法的最短路径问题求解:一种是Win32 Console Application，输入输出采用传统DOS的字符式交互界面；另一种是MFC AppWizard(exe），输入输出采用基于Windows的图形式交互界面。编写DOS相关算法时采用类与对象进行编程，定义类MGraph，包含的数据元素有顶点信息、邻接矩阵和顶点数和边数，还包括成员函数void CreateMGraph（MGraph ＆）；用于构造有向图、void Ppath（int[］[100]，int，int）；、void Dispath(int［］［100］，int[]［100],int)；实现输出最短路径、void Floyd（MGraph G）;则是Floyd算法的具体实现。通过定义对象对成员函数进行调用，完成基于floyd算法求最短路径问题.MFC虽然算法复杂,但是基于MFC的应用程序能更形象直接的供用户使用。
最后要感谢老师和同学的帮助，我才能成功的完成这次课程设计的论文.这次课程设计作为学完面向对象程序设计课程后的一次全面的综合练习。通过这次设计增加我对面向对象程序设计的基础理论的理解，掌握面向对象程序设计开发的基本方法，进一步提高了综合运用所学知识的能力。
参考文献
[1］ 谭浩强．C++基础入门大全．北京：清华大学出版社,2012:100-102
［2］ 郑莉,董渊，张瑞丰．C++语言程序设计（第3版）．北京:清华大学出版社，2007:25-60
［3］ 钱能．C++程序设计教程（第2版）．北京:清华大学出版社，2007：100—130
[4］ 欧阳志宏,董霖，钟俊华．MFC程序设计轻松入门．北京：人民邮电出版社,2009
［5]严蔚敏，吴伟民．数据结构（C语言版）．北京：清华大学出版社,2007：168-192
19