基于Floyd算法的最短路径问题的求解c++
摘要
现实生活中许多实际问题的解决依赖于最短路径的应用，其中比较常用的是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)
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:
公用的数据和成员函数；
}；
定义对象：类名对象名；
可以在类外定义成员函数，在函数名前加上类名，“：：”是作用域限定符或称作用域运算符用它说明函数式属于哪个类的。如下面程序中的
void MGraph::CreateMGraph(MGraph &G)
{
函数体
}
3.2 类的接口设计
#include
#include
#include
using namespace std;
#define MaxVertexNum 100
#define INF 32767
class MGraph
{private:
char vertex[MaxVertexNum]; //顶点信息
int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵
int n,e; //顶点数和边数
public:
void CreateMGraph(MGraph &); //构造有向图
void Ppath(int[][100],int,int);
void Dispath(int[][100],int[][100],int); //输出最短路径
void Floyd(MGraph G); //Floyd算法的具体实现};
首先将所需文件名写好，定义类MGraph。在进行类体构造时将数据char vertex[MaxVertexNum]、int edges[MaxVertexNum][MaxVertexNum]和int n,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)//构造有向图
{
int i,j,k,p;
cout<<"请输入顶点数和边数:";
cin>>G.n>>G.e;
cout<<"请输入顶点元素:";
for (i=0;i { cin>>G.vertex[i]; } for (i=0;i { for (j=0;j { G.edges[i][j]=INF; if (i==j) { G.edges[i][j]=0; } } } for (k=0;k { cout<<"请输入第"< cin>>i>>j>>p; G.edges[i][j]=p; } } void MGraph::Ppath(int path[][MaxVertexNum],int i,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)//输出最短路径的算法 { int i,j; for (i=0;i { for (j=0;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); } } } } void MGraph::Floyd(MGraph G) { int A[MaxVertexNum][MaxVertexNum],path[MaxVertexNum][MaxVertexNum]; int i,j,k; for (i=0;i { for (j=0;j { A[i][j]=G.edges[i][j]; path[i][j]=-1; } } for (k=0;k { for (i=0;i { for (j=0;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所示。 控件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); //****************************获得文件名************************// //CString strFileName; 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); } //将文件的数据读入到数组中 CStdioFile fp; if(!fp.Open(m_strFileInfo,CFile::modeRead)) {MessageBox("文件打开失败!"); return; } int i=0; CString str; 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 {if(tp[i] != -1) c[i/n+1][i%n+1] = tp[i]; else c[i/n+1][i%n+1] = maxint; } UpdateData(FALSE); } void CEx_exFloydDlg::Ex_floyd(int n,int **c,int **a,int **r) { int i,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][k]+a[k][j]; r[i][j]=k; } } } int CEx_exFloydDlg::Ex_output(int **r,int i,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); //接受编辑框的数据 CString strData; 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中的主要代码为： class CEx_exFloydDlg : public CDialog { // Construction public: CEx_exFloydDlg(CWnd* pParent = NULL); // standard constructor void Ex_floyd (int n,int **c,int **a,int **r); int Ex_output(int **r,int i,int j); // Dialog Data //{{AFX_DATA(CEx_exFloydDlg) enum { IDD = IDD_EX_EXFLOYD_DIALOG }; CString m_strFileInfo; int m_intEnd; int m_intStart; CString m_strResult; int m_nNUM; protected: HICON m_hIcon; int n ; //图形中顶点的个数 int **a; //最优值矩阵 int **c;//顶点之间的距离矩阵 int **r;//路由矩阵 int counts; int *tp; CString strRes; // 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）两个外部调用函数模块： void CEx_exFloydDlg::Ex_floyd(int n,int **c,int **a,int **r) {int i,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][k]+a[k][j]; r[i][j]=k; } } } int CEx_exFloydDlg::Ex_output(int **r,int i,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); } //将文件的数据读入到数组中 CStdioFile fp; if(!fp.Open(m_strFileInfo,CFile::modeRead)) {MessageBox("文件打开失败!"); return; } int i=0; CString str;