法的基本思维是递推产生一个矩阵序列A0，A1，A2，….Ak，… An，其中Ak[i][j]表示从顶点到vi到顶点vj的路径上所经过的顶点编号不大于k的最短路径长度。
A[i][j]=cost[i][j]
A(k+1)[i][j]=min{Ak[i][j],Ak[i+1][k+1]+Ak[k+1][j]}
弗洛伊德主要算法，若Ak[i][j]已求出，顶点i到顶点k+1的路径长度为Ak[i][k+1]，顶点路径长度为Ak[i][j]，顶点k+1到顶点j的路径长度为Ak[k+1][j]，如果此时Ak[i][k+1]+Ak[k+1][j]< Ak[i][j],则将原来的顶点i到顶点j的路径改为顶点，否则不需要修改顶点i到j的路径。
k+1 j Ak[i,k+1] Ak[k+1,j]
i Ak[i,j] 图2-6 若Ak[i][k+1]+Ak[k+1][ j]< Ak[i][j],修改路径 过程：
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{ if(D[i][k]+D[k][j] D[i][j]=D[i][k]+D[k][j]; //修改长度 P[i][j]=P[i][k]; 2.3主函数的调用关系图 程序是通过进入程序之后，用户开始根据自己的实际情况来输入具体的地图参数，构建自己所需要的地图大小以及城市个数和路径长短。当输入完毕参数之后，用户进入主菜单查询界面。可根据不同的选口令，用户可以选择不同的系统功能。 查询1可以进入狄克斯特函数，来求取得到一个城市到所有城市自己还能的具体的最短路径以及走法。当用户输入口令2之后，可以进入弗洛伊德函数的调 用，更加提示用户输入想要查询的两个城市，系统会根据地图自动计算出所需要的最短距离以及最短路径，完美的满足用户自己的需求。当输入口令0之后，用户可以选择退出程序，结束城市查询。同时由于地图的邻接矩阵建立是由malloc函数申请的空间，在结束运行之后，系统自动释放空间，从而减少系统空间的占有率。 开始 输入参数 0 1 选择查询 信息 弗洛伊德 图2-7 结束 退出 输出结果 输出结果 狄克斯特 2 3.系统测试 3.1操作说明 双击“城市交通咨询系统.exe”，根据屏幕菜单提示信息，选择任意可选项进行相关操作。根据提示开始输入城市个数以及路径总个数。之后开始建立地图，建立成功后根据菜单界面选择功能。 3.2测试数据 输入测试数据可以对程序进行如下的图的数据进行数据测试。 8 1 2 4 6 5 3 6 7 图3-1 4 下面运行程序检查输入，输出结果。 3.2.1用户进入界面： （1）、输入城市个数与路径个数 图3-2 （2）输入具体的顶点以及边的个数： 图3-3 地图输入完成，有向图存储结构建立完成。 3.2.2、具体功能的实现 1、求一个城市到所有城市之间的最短距离。 查询一个顶点到其他顶点的最短路径。如下图。经过手工计算： 1=>1 长度=0，1=>2 长度=8，1=>3 长度=8+6=14，1=>4 长度=8+5=13；和下图完全一致 图3-4 为保证结果正确换一个顶点进行：如顶点2到其他的距离 经过手工计算：2=>1 长度=6+4=10，2=>2 长度=0，2=>3 长度=6，2=>4 长度=5；和下图完全一致 图3-5 2、求任意的两个城市之间的最短距离 例1到3之间的最短距离，经过计算可得最短距离为1=>2=>3，且路径 为14，与下图结果相同。 图3-6 为保证结果正确换一个顶点进行：如顶点2到4之间的最短路径以及距离 经过计算可得2到4的最短路径是2=>4,且最短路径为5 图3-7 3.2.3、结束程序 当用户输入命令0时，结束程序 图3-8
相关推荐：
loading