运筹学最短路径实验

运筹学课程设计报告姓名：一、算法思想运用Dijkstra算法求解图的最短路径。

Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S 表示，初始时S中只有一个源点，以后每求得一条最短路径, 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。

在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。

此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

二、算法流程或步骤Dijkstr算法具体步骤：（1）初始时，S只包含源点，即S＝，v的距离为0。

U包含除v 外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或）（若u不是v的出边邻接点）。

（2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

（4）重复步骤（2）和（3）直到所有顶点都包含在S中。

三、算法源程序#include <iostream.h>int m;int n;float a[100][100];float dist[100];int prev[100];float MAX_V ALUE=10000;void dijkstra(){if(m<0||m>n) //当无顶点的情况return;bool *s=new bool[n+1];for(int i=0;i<n;i++){dist[i]=a[0][i]; //与源点相连的权值s[i]=false;if(dist[i]==MAX_V ALUE) //与源点无连接的顶点prev[i]=0; //设置对应权值为elseprev[i]=m; //与源点相连接的顶点设置为m }dist[m]=0;s[m]=true;for(int i1=0;i1<n;i1++){float temp=MAX_V ALUE;int u=m;for(int j=0;j<n;j++)if((!s[j])&&(dist[j]<temp))//与源点相连的顶点{u=j;temp=dist[j]; //设置temp成为与源点相连的顶点权值}s[u]=true;for(int j1=0;j1<n;j1++)if((!s[j1])&&(a[u][j1]<MAX_V ALUE)){float newdist=dist[u]+a[u][j1]; //算出与源点不直接相连的权值和if(newdist<dist[j1]){dist[j1]=newdist;prev[j1]=u;}}}}void path(){for(int i=0;i<n;i++)if(i!=m&&dist[i]<MAX_V ALUE){cout<<"由源到顶点"<<i<<"的最短路径为：(终点位置) "<<i;int temp=i;do{temp=prev[temp];cout<<" <-- "<<temp;}while(temp!=m);cout<<" (源位置)。

最短路径的实验报告最短路径的实验报告引言：最短路径问题是图论中一个经典的问题，涉及到在一个带有权重的图中找到两个顶点之间的最短路径。

本实验旨在通过实际操作和算法分析，深入探讨最短路径算法的性能和应用。

实验设计：本次实验使用了Dijkstra算法和Floyd-Warshall算法来解决最短路径问题。

首先，我们使用Python编程语言实现了这两个算法，并对它们进行了性能测试。

然后，我们选择了几个不同规模的图进行实验，以比较这两种算法的时间复杂度和空间复杂度。

最后，我们还在实际应用中使用了最短路径算法，以验证其实用性。

实验过程：1. 实现Dijkstra算法Dijkstra算法是一种贪心算法，用于求解单源最短路径问题。

我们首先实现了该算法，并对其进行了性能测试。

在测试中，我们使用了一个包含1000个顶点和5000条边的图，记录了算法的运行时间。

结果显示，Dijkstra算法的时间复杂度为O(V^2)，其中V表示图中的顶点数。

2. 实现Floyd-Warshall算法Floyd-Warshall算法是一种动态规划算法，用于求解所有顶点对之间的最短路径。

我们在Python中实现了该算法，并对其进行了性能测试。

在测试中，我们使用了一个包含100个顶点和5000条边的图，记录了算法的运行时间。

结果显示，Floyd-Warshall算法的时间复杂度为O(V^3)，其中V表示图中的顶点数。

3. 比较两种算法通过对Dijkstra算法和Floyd-Warshall算法的性能测试，我们可以看到，Dijkstra算法在处理较大规模的图时性能更好，而Floyd-Warshall算法在处理较小规模的图时性能更好。

因此，在实际应用中，我们可以根据图的规模选择合适的算法。

4. 应用实例为了验证最短路径算法的实际应用性，我们选择了一个城市交通网络图进行实验。

我们使用了Dijkstra算法来计算两个城市之间的最短路径，并将结果与实际的驾车时间进行比较。

实验三最短路径的算法（离散数学实验报告）实验3：最短路径算法⼀、实验⽬的通过本实验的学习，理解Floyd（弗洛伊得）最短路径算法的思想⼆、实验内容⽤C语⾔编程实现求赋权图中任意两点间最短路径的Floyd算法，并能对给定的两结点⾃动求出最短路径三、实验原理、⽅法和⼿段1、Floyd算法的原理定义：Dk[i,j] 表⽰赋权图中从结点vi出发仅通过v0，v1，┉，vk-1中的某些结点到达vj的最短路径的长度，若从vi到vj没有仅通过v0，v1，┉，vk-1 的路径，则D[i,j]=∝即D-1[i,j] 表⽰赋权图中从结点vi到vj的边的长度，若没有从结点vi到vj的边，则D[i,j]=∝D0[i,j] 表⽰赋权图中从结点vi到vj的”最短”路径的长度, 这条路上除了可能有v0外没有其它结点D1[i,j] 表⽰赋权图中从结点vi到vj的”最短”路径的长度, 这条路上除了可能有v0，v1外没有其它结点┉┉┉根据此定义，D k[i,j]=min{ D k-1[i,j] , D k-1[i,k-1]+D k-1[k-1,j] }定义：path[i,j]表⽰从结点vi到vj的“最短”路径上vi的后继结点四、实验要求要求输出每对结点之间的最短路径长度以及其最短路径五、实验步骤（⼀）算法描述Step 1 初始化有向图的成本邻矩阵D、路径矩阵path若从结点vi到vj有边，则D[i,j]= vi到vj的边的长度，path[i,j]= i；否则D[i,j]=∝，path[i,j]=-1Step 2 刷新D、path 对k=1,2,┉n 重复Step 3和Step 4Step 3 刷新⾏对i=1,2,┉n 重复Step 4Step 4 刷新Mij 对j=1,2,┉n若D k-1[i,k]+D k-1[k,j][结束循环][结束Step 3循环][结束Step 2循环]Step 5 退出（⼆）程序框图参考主程序框图其中，打印最短路径中间结点调⽤递归函数dist()，其框图如下，其中fist,end是当前有向边的起点和终点dist(int first, int end)七、测试⽤例：1、输⼊成本邻接矩阵：D ：06380532290141003210∝∝∝∝V V V V V V V V （其中∝可⽤某个⾜够⼤的数据值代替，⽐如100）可得最短路径矩阵：P ：131132122211111010103210--------V V V V V V V V以及各顶点之间的最短路径和最短路径长度：从V0到V1的最短路径长度为：1 ；最短路径为：V0→V1 从V0到V2的最短路径长度为：9 ；最短路径为：V0→V1→V3→V2 从V0到V3的最短路径长度为：3 ；最短路径为：V0→V1→V3 从V1到V0的最短路径长度为：11；最短路径为：V1→V3→V2→V0从V1到V2的最短路径长度为：8 ；最短路径为：V1→V3→V2 从V1到V3的最短路径长度为：2 ；最短路径为：V1→V3 从V2到V0的最短路径长度为：3 ；最短路径为：V2→V0 从V2到V1的最短路径长度为：4 ；最短路径为：V2→V0→V1 从V2到V3的最短路径长度为：6 ；最短路径为：V2→V0→V1→V3 从V3到V0的最短路径长度为：9 ；最短路径为：V3→V2→V0 从V3到V1的最短路径长度为：10；最短路径为：V3→V2→V0→V1 从V3到V2的最短路径长度为：6 ；最短路径为：V3→V2 参考程序： #include #define INFINITY 100 #define Max 10int a[Max][Max],P[Max][Max]; main() {void Print_Flod(int d);int i,j,k,D=4;printf("请输⼊成本邻接矩阵：\n");for(i=0;ifor(j=0;j{scanf("%d",&a[i][j]);}for(i=0;ifor(j=0;j{if(a[i][j]>0&& a[i][j]elseP[i][j]=-1;}for(k=0;kfor(i=0;ifor(j=0;jif (a[i][k]+a[k][j]{a[i][j]=a[i][k]+a[k][j];P[i][j]=k;}Print_Flod(D);}void Print_Flod(int d){void dist(int first,int end);int i,j;for(i=0;ifor(j=0;jif(i!=j){ printf("from V%d to V%d: ",i,j); dist(i,j);printf("V%d",j);printf(" (The length is: %d)\n",a[i][j]); }}void dist(int first,int end){ int x;x=P[first][end];if(x!=first){ dist(first,x); dist(x,end); }else printf("V%d->",x);}输出结果：。

最短路径实验报告最短路径实验报告引言：最短路径算法是计算机科学中的一个经典问题，它在许多领域中都有广泛的应用，如交通规划、电路设计、网络通信等。

本实验旨在通过实践探索最短路径算法的实际应用，并对其性能进行评估。

一、问题描述：我们将研究一个城市的交通网络，其中包含多个节点和连接这些节点的道路。

每条道路都有一个权重，表示通过该道路所需的时间或距离。

我们的目标是找到两个节点之间的最短路径，即使得路径上各个道路权重之和最小的路径。

二、算法选择：为了解决这个问题，我们选择了Dijkstra算法和Floyd-Warshall算法作为比较对象。

Dijkstra算法是一种单源最短路径算法，它通过不断选择当前最短路径的节点来逐步扩展最短路径树。

Floyd-Warshall算法则是一种多源最短路径算法，它通过动态规划的方式计算任意两个节点之间的最短路径。

三、实验设计：我们首先构建了一个包含10个节点和15条道路的交通网络，每条道路的权重随机生成。

然后，我们分别使用Dijkstra算法和Floyd-Warshall算法计算两个节点之间的最短路径，并记录计算时间。

四、实验结果：经过实验，我们发现Dijkstra算法在计算单源最短路径时表现出色，但是在计算多源最短路径时效率较低。

而Floyd-Warshall算法在计算多源最短路径时表现出色，但是对于大型网络的单源最短路径计算则需要较长的时间。

五、性能评估：为了评估算法的性能，我们对不同规模的交通网络进行了测试，并记录了算法的计算时间。

实验结果显示，随着交通网络规模的增大，Dijkstra算法的计算时间呈指数级增长，而Floyd-Warshall算法的计算时间则呈多项式级增长。

因此，在处理大型网络时，Floyd-Warshall算法具有一定的优势。

六、实际应用：最短路径算法在实际应用中有着广泛的用途。

例如，在交通规划中，最短路径算法可以帮助我们找到最优的行车路线，减少交通拥堵。

实验报告填写说明
（实验项目名称、实验项目类型必须与实验教学大纲保持一致）
1．实验环境：
实验用的硬件、软件环境。

2．实验目的：
根据实验教学大纲，写出实验的要求和目的。

3．实验原理：
简要说明本实验项目所涉及的理论知识。

4．实验步骤：
这是实验报告极其重要的容。

对于验证性验，要写清楚操作方法，需要经过哪几个步骤来实现其操作。

对于设计性和综合性实验，还应写出设计思路和设计方法。

对于创新性实验，还应注明其创新点。

5．实验结论：
根据实验过程中得到的结果，做出结论。

6．实验总结：
本次实验的收获、体会和建议。

7．指导教师评语及成绩：
指导教师依据学生的实际报告内容，给出本次实验报告的评价和成绩。

附录1：源程序。

实验一最短路径求解最短路径求解
实验一：最短路径求解
实验目的：利用Excel 线性规划求解最短思路。

实验环境：Microsoft Excel2003，Windows XP。

实验注意事项：
实验内容：使用线性规划计算机程序求解图1.1网络拓扑图中s
点到t 点间的最短路径。

图1.1 网络拓扑图
实验步骤：
1. 添加“规划求解”项，可通过“工具” “加载宏”加入该项
功能。

2. 将网络拓扑图转化成关联矩阵
A 矩阵表示各节点与各边相接的连接关系，若边e i 与节点v i
无关联则在此型式为0；若边e i 表示从节点v i 流出为1，若边e i 表示从节点v i 流入为-1。

列出各弧长向量W ：
A 矩阵与向量W 出更可完整描述出数据流结构。

3. 根据Bellman 方程和约束条件进行求解
约束条件：若形成两点之间的最长路径，则起点s 必有一出路径，终点t 必有一入路径，其他中间节点必然一进有一进一出的路径。

Bellman 方程中Xi 向量为求解目标，Xi 代表此边是否在最短路
径上，如在最短路径上测度为1，若不在取值为0。

4. 使用Excel 线性规划求解，选择主菜单的“工具” “规划求解”即可进入“规划求解
参数”定义窗口；
其中目标单元格为Wi ×Xi ，可变单元格为Xi ，约束条件为Xi ≤1，且为整数；
AXi 表示向量值为Bellman 方程中所示（这里为方便求解，特将
s 点的AXs 值-1，将t 点的AXt 值+1，这样约束向量AXi=『0，0，0，0』）。

点击“求解”可得规划目标。

云南财经大学信息学院学生综合性与设计性实验报告（2013—2014 学年第 2 学期）一、实验内容与目的1.内容查看“最短路径.swf”，选择熟悉的程序设计语言定义有向图，根据动画演示求取从有向图任一结点到其他结点的最短路径。

2.实验目的了解最短路径的概论，掌握求最短路径的方法。

二、实验原理或技术路线（可使用流程图描述）实验原理：(李燕妮负责设计，周丽琼负责编程)图是由结点的有穷集合V和边的集合E组成，求最短路径用迪杰斯特拉算法：1)适用条件&范围：a) 单源最短路径(从源点s到其它所有顶点v);b) 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)c) 所有边权非负(任取(i,j)∈E都有Wij≥0);2)算法描述：a)初始化：dis[v]=maxint(v∈V,v≠s); dis[s]=0; pre[s]=s; S={s};b)For i:=1 to n1.取V-S中的一顶点u使得dis[u]=min{dis[v]|v∈V-S}2.S=S+{u}3.For V-S中每个顶点v do Relax(u,v,Wu,v)c)算法结束：dis[i]为s到i的最短距离；pre[i]为i的前驱节点三、实验环境条件（使用的软件环境）Microsoft Visual C++6.0四、实验方法、步骤（列出程序代码或操作过程）/*本程序的功能是求图中任意两点间的最短路径*/#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<string.h>#define ING 9999typedef struct ArcCell{int adj;/*顶点关系类型，用1表示相邻，0表示不相邻*/}ArcCell,**AdjMatrix;/*邻接矩阵*/typedef struct type{char data[3];/*顶点值*/}VertexType;typedef struct{VertexType *vexs; /*顶点向量*/AdjMatrix arcs; /*邻接矩阵*/int vexnum,arcnum; /*图的顶点数和边数*/}MGraph;/*初始图*/void InitGraph(MGraph *G){int i,nu,mu;printf("\n输入顶点的个数和（边）弧的个数：");scanf("%d %d",&nu,&mu);G->arcs=(ArcCell **)malloc(nu*sizeof(ArcCell *));for(i=0;i<nu;i++)/*分配邻接矩阵空间*/G->arcs[i]=(ArcCell *)malloc(nu*sizeof(ArcCell));G->vexs=(VertexType *)malloc(nu*sizeof(VertexType)); /*分配顶点空间*/ G->vexnum=nu;G->arcnum=mu; /*图的顶点数和边数*/}void InsertGraph(MGraph *G,int i,VertexType e){if(i<0||i>G->vexnum) return;strcpy(G->vexs[i].data,e.data);}/*确定v1在图顶点中的位置*/int Locate(MGraph G,VertexType v1){int i;for(i=0;i<G.vexnum;i++)if(strcmp(v1.data,G.vexs[i].data)==0) return i;return -1;}/*采用数组（邻接矩阵）和邻接表表示无向图*/void CreateUND(MGraph *G){int i,j,k,*p,w;VertexType v1,v2;p=(int *)malloc(G->vexnum*sizeof(int));for(i=0;i<10;i++) p[i]=0;for(i=0;i<G->vexnum;++i) /*初始邻接表*/{for(j=0;j<G->vexnum;++j)G->arcs[i][j].adj=ING;}for(k=0;k<G->arcnum;++k){printf("\n输入第%d 条（边）弧相对的两个顶点值:\n",k+1);scanf("%s %s",v1.data,v2.data);/*输入相邻的两个点值*/printf("输入它们的权值: ");scanf("%d",&w);i=Locate(*G,v1);j=Locate(*G,v2); /*用i 和j来确定它们的位置*/G->arcs[i][j].adj=w;}}/*输出邻接矩阵*/void Pint(MGraph G){int i,j;for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){if(G.arcs[i][j].adj!=ING)printf("\t%d",G.arcs[i][j].adj);else{if(i==j)printf("\t0");else printf("\t∞");}}printf("\n");}}/*对顶点V0到其余顶点v的最短路径p[v]及其带权长度D[v]若p[v][w]为1，则w是从V0到W当前求得最短路径上的顶点, final[v]为1，当且仅当v属于S，即已经求得从v0到v的最短路*/void ShortestPath(MGraph G,int v0,int **p,int *D){int v,u,i,w,min;int *final;final=(int *)malloc(G.vexnum*sizeof(int));/*分配空间*/for(v=0;v<G.vexnum;++v){final[v]=0;D[v]=G.arcs[v0][v].adj;/*初始化*/for(w=0;w<G.vexnum;++w) p[v][w]=0;/*设空路径*/if(D[v]<ING){p[v][v0]=1;p[v][v]=1;}/*v到v0有路径*/}D[v0]=0;final[v0]=1;/*初始化，V0顶点属于S集*/for(i=1;i<G.vexnum;i++){/*其余G.vexnum-1个顶点*/min=ING;for(w=0;w<G.vexnum;++w) /*求出矩阵这一行的最小值*/ if(!final[w]) /*W顶点属于V-S中*/if(D[w]<min){v=w;min=D[w];}final[v]=1;/*离V0顶点最近的V加入S集*/for(w=0;w<G.vexnum;++w) /*更新当前最短路径及距离*/ if(!final[w]&&(min+G.arcs[v][w].adj<D[w])){ /*不是最小的，修改D[w],P[w]*/D[w]=min+G.arcs[v][w].adj;for(u=0;u<G.vexnum;u++)p[w][u]=p[v][u];p[w][w]=1;}}free(final);}void main(){MGraph G;VertexType e;int i,j;int **p;int *D;InitGraph(&G);p=(int **)malloc(G.vexnum*sizeof(int *));for(i=0;i<G.vexnum;i++)p[i]=(int *)malloc(G.vexnum*sizeof(int));D=(int *)malloc(G.vexnum*sizeof(int));printf("顶点值：\n");for(i=0;i<G.vexnum;++i)/*给图顶点向量付值*/{scanf("%s",e.data);InsertGraph(&G,i,e);}CreateUND(&G);/*构造图结构*/printf("邻接矩阵为：\n");Pint(G);for(i=0;i<G.vexnum;i++) /*输出邻接矩阵*/{ShortestPath(G,i,p,D); /*调用最短函数*/for(j=0;j<G.vexnum;j++)if(i!=j) printf(" %s 到%s 的最短路径为%d \n",G.vexs[i].data,G.vexs[j].data,D[j]);printf("\n\n");}getch();}五、实验过程原始记录( 测试数据、图表)请给出各个操作步骤的截图和说明，要求有对时间复杂度和空间复杂度的说明。

实验八最短路径实验一、实验目的通过最短路径求解的实验，帮助学生熟练掌握图的顶点和边的概念，以及其存储实现；掌握图的基本运算和利用图解决实际问题的基本方法。

二、实验内容以严蔚敏《数据结构（C语言版）》教科书图7.33交通图为例，求解最短路径。

具体内容包括：1、用文本文件组织图的顶点和图的边。

2、图的存储表示：从文件中输入图的顶点和图的边，并转换为图的存储结构表示。

3、求解交通图的最短路径，并用文件保存图的最短途径数据。

4、求解从一个城市出发到其它所有城市的最短路径。

5、求解从一个城市到另一个城市的最短路径。

三、实验仪器微型计算机实验用编程语言：Turbo C 2.0，Borland C 3.0等以上版本四、实验原理图是顶点的集合和边的集合。

边定义了顶点之间的关系。

1、图的存储表示（1）图的顶点的表示在交通图中，图的一个顶点表示一个城市的名字。

城市的名字用一个字符串表示。

因此，图的顶点集用一个二维字符数组表示，也可以说以字符串为单位的一维数组表示。

用C语言定义为：char city[CityNum][NameLenght];图的顶点在图中的位置用顶点名（城市名）在一维顶点向两种的序号表示。

顶点在图的位置（序号）与顶点的输入顺序有关。

对于同一个图，顶点的输入顺序不同，顶点在图中的位置不同，但不影响计算结果。

（2）图的边的表示在交通图中，边表示城市之间的交通线路，在本例中假设交通线路为铁路。

边上的权值表示铁路的长度（公里数）。

考虑铁路都是双向行使，交通图用无向图来表示。

为了方便求的任给两个城市是否有铁路相连，以及铁路的长度，用邻接矩阵表示交通图中各城市之间的邻接关系。

用C语言定义为：int arc[CityNum][CityNum]（3）图的总体存储表示图的总体存储表示定义如下：#define CityNum 30 //最大城市结点数#define NameLenght 12 //城市名字长度#define Infinity 10000 //若城市间没有路径距离设定为Infinitytypedef char Vextype[NameLenght];typedef int Arctype;typedef struct{ Vextype vexs[CityNum]; // 顶点数组Arctype arcs[CityNum][CityNum]; //边矩阵，权值w ijint vexnum,arcnum; //顶点数,边数} Mgraph2、最短路径的表示最短路径值用矩阵表示，其定义如下：int dist[CityNum][CityNum]其中，dist[i][j]表示第i个城市到第j个城市的最短路径值路径顶点序列用路径矩阵表示，定义如下：int Path[CityNum][CityNum]其中，Path[i][j]表示第i个城市到第j个城市的路径上，第j个城市的前一个城市（序号）。

HUNAN UNIVERSITY 课程实习报告题目最短路径问题学生姓名学生学号专业年级指导老师完成日期一、需求分析本实验是求最短路径的问题，从文件中读入有向网中顶点的数量和顶点间的票价的矩阵，以用户指定的起点，在文件中输出到其余各顶点的最短路径及花费。

（1）输入：输入的形式：（文件）5-1 10 3 20 -1-1 -1 -1 5 -1-1 2 -1 -1 15-1 -1 -1 -1 11-1 -1 -1 -1 -1（用户）输入起点：0输入值的范围：文件输入中，顶点数和矩阵中顶点间的票价均为整型int，用户输入中，起点数为整型int。

（2）输出的形式：（文件）源点0到顶点1的最小花费为:5路径为：0——>2——>1源点0到顶点2的最小花费为:3路径为：0——>2源点0到顶点3的最小花费为:10路径为：0——>2——>1——>3源点0到顶点4的最小花费为:18路径为：0——>2——>4（3）程序所达到的功能：在文件中给出有向网的顶点个数和顶点间的票价的矩阵，以用户指定的起点，在文件中输出起点到其余各顶点的最短路径及花费。

（4）测试数据：a.输入：（文件）5-1 10 3 20 -1-1 -1 -1 5 -1-1 2 -1 -1 15-1 -1 -1 -1 11-1 -1 -1 -1 -1（用户）输入起点：0输出：（文件）源点0到顶点1的最小花费为:5路径为：0——>2——>1源点0到顶点2的最小花费为:3路径为：0——>2源点0到顶点3的最小花费为:10路径为：0——>2——>1——>3源点0到顶点4的最小花费为:18路径为：0——>2——>4b.输入：（文件）5-1 10 3 20 -1-1 -1 -1 5 -1-1 2 -1 -1 15-1 -1 -1 -1 11-1 -1 -1 -1 -1（用户）输入起点：2输出：（文件）源点2到顶点0：没有连通路径源点2到顶点1的最小花费为:2路径为：2——>1源点2到顶点3的最小花费为:7路径为：2——>1——>3源点2到顶点4的最小花费为:15路径为：2——>4c.输入：（文件）618 10 3 20 -1 915 -1 -1 5 -1 -1-1 20 16 -1 -1 15-1 -1 30 -1 6 32 9 -1 20 -1 -1-1 8 12 -1 -1 5（用户）输入起点：5输出：（文件）源点5到顶点0的最小花费为:21路径为：5——>1——>3——>4——>0源点5到顶点1的最小花费为:8路径为：5——>1源点5到顶点2的最小花费为:12路径为：5——>2源点5到顶点3的最小花费为:13路径为：5——>1——>3源点5到顶点4的最小花费为:19路径为：5——>1——>3——>4d.输入：（文件）618 10 3 20 -1 915 -1 -1 5 -1 -1-1 20 16 -1 -1 15-1 -1 30 -1 6 32 9 -1 20 -1 -1-1 8 12 -1 -1 5（用户）输入起点：3输出：（文件）源点3到顶点0的最小花费为:8路径为：3——>4——>0源点3到顶点1的最小花费为:11路径为：3——>5——>1源点3到顶点2的最小花费为:11路径为：3——>4——>0——>2源点3到顶点4的最小花费为:6路径为：3——>4源点3到顶点5的最小花费为:3路径为：3——>5e.输入：（文件）3-1 -1 -1-1 -1 -1-1 -1 -1（用户）输入起点：1输出：（文件）源点1到顶点0：没有连通路径源点1到顶点2：没有连通路径f.输入：（文件）3-1 -1 -1-1 -1 -1-1 -1 -1（用户）输入起点：3输出：（文件）源点3到顶点0的最小花费为:-572562307路径为：3——>1——>0源点3到顶点1的最小花费为:-572662307路径为：3——>1源点3到顶点2的最小花费为:-572662307路径为：3——>2二、概要设计（1）所有抽象数据类型的定义：const int MaxNum=100000;//利用邻接矩阵存储图：class Graph{private:int *Adj;//保存邻接矩阵的一维数组j和k之间权值存储在Adj[j*Num+k]中int Num;public:Graph();~Graph();void Floyd(int start);};（2）算法的基本思想：采用邻接矩阵为图的存储结构，保存邻接矩阵的一维数组j和k之间权值存储Adj[j*Num+k]中，以用户指定的起点，进行弗洛伊德算法，先初始化最短路径，对角线元素设置为0，其他元素设置为边的权值，没有有向边设置为MaxNum，依次插入中间点k，判断是否检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，若不成立则路径不改变，若成立则更新最短路径，设置Dis(i,j) = Dis(i,k) + Dis(k,j)，直至循环结束，更新后的最短路径入栈，在文件中输出到其余各顶点的最短路径及花费。