下载文档原格式
邻接矩阵求最短路径c语言邻接矩阵表示图中各个节点之间的关系，在求解最短路径问题中，邻接矩阵是非常重要的数据结构之一。
下面是一个简单的C语言程序，用于利用邻接矩阵求解最短路径问题。
首先，我们需要定义一个邻接矩阵。
假设我们有一个图，其中有5个节点，节点编号从1到5，邻接矩阵可以表示为一个5x5的二维数组，其中arr[i][j]表示从节点i到节点j的距离。
如果两个节点之间没有直接的边，则arr[i][j]的值为无穷大。
接下来，我们需要使用Dijkstra算法来求解最短路径。
该算法使用贪心策略，在每一次迭代中，选择当前距离源点最近的节点，并以该节点为中心更新其周围的节点的距离。
具体实现如下：1. 定义一个长度为n的数组dist，其中dist[i]表示从源点到节点i的距离。
2. 将dist数组初始化为无穷大，源点的dist值为0。
3. 定义一个长度为n的数组visited，标记已经被访问过的节点。
4. 循环n次，每次选择一个距离源点最近的未被访问过的节点u。
5. 标记节点u为已经访问过。
6. 遍历节点u的所有邻居v，如果从源点到v的距离通过u可以更新，则更新dist[v]的值。
7. 返回dist数组，即为从源点到各个节点的最短距离。
下面是一个简单的C语言程序，用于实现邻接矩阵求最短路径的功能。
```c#include <stdio.h>#define INF 99999#define MAX_N 100int arr[MAX_N][MAX_N]; //邻接矩阵int dist[MAX_N]; //存储最短距离int visited[MAX_N]; //标记已经被访问过的节点int n; //节点数int minDistance() {int minDist = INF;int minIndex = -1;for (int i = 0; i < n; i++) {if (visited[i] == 0 && dist[i] < minDist) {minDist = dist[i];minIndex = i;}}return minIndex;}void dijkstra(int start) {//初始化dist数组和visited数组for (int i = 0; i < n; i++) {dist[i] = INF;visited[i] = 0;}dist[start] = 0;for (int i = 0; i < n - 1; i++) {int u = minDistance();visited[u] = 1;for (int v = 0; v < n; v++) {if (visited[v] == 0 && arr[u][v] != INF && dist[u] + arr[u][v] < dist[v]) {dist[v] = dist[u] + arr[u][v];}}}}int main() {//初始化邻接矩阵n = 5;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {arr[i][j] = INF;}}arr[0][1] = 10;arr[0][4] = 5;arr[1][2] = 1;arr[1][4] = 2;arr[2][3] = 4;arr[3][2] = 6;arr[3][0] = 7;arr[4][1] = 3;arr[4][2] = 9;arr[4][3] = 2;//执行Dijkstra算法dijkstra(0);//输出结果for (int i = 0; i < n; i++) {printf('从节点0到节点%d的最短距离是%d ', i, dist[i]);}return 0;}```代码中，我们使用了INF表示两个节点之间没有直接的边。
Ｄｉｊｋｓｔｒａ最短路径算法的实现及优化 施培港 厦门信息港建设发展股份有限公司 厦门市槟榔路１号联谊广场五层 ３６１００４ Ｅｍａｉｌ：ｓｐｇ＠ｘｍｉｎｆｏｐｏｒｔ．ｃｏｍ 摘要：最短路径算法种类繁多，比较有名的算法包括：Ｄｉｊｋｓｔｒａ算法、Ｆｏｒｄ算法、Ｆｌｏｙｄ算法、Ｍｏｏｒｅ算法、Ａ＊算法、Ｋ值算法，而即使同一种算法也有多种不同的实现方式。
本文就Ｄｉｊｋｓｔｒａ算法的两种实现方式做一定的分析，并采用一种新的实现方法达到对算法优化的目的。
关键字：Ｄｉｊｋｓｔｒａ算法 最短路径 网络分析 地理信息系统（ＧＩＳ） １． 何谓最短路径 所谓最短路径就是网络中两点之间距离最短的路径，这里讲的距离可以是实际的距离，也可以引申为其它的度量，如时间、运费、流量等。
因此，从广义上讲，最短路径算法就是指从网络中找出两个点之间最小阻抗路径的算法。
２． Ｄｉｊｋｓｔｒａ算法介绍 Ｄｉｊｋｓｔｒａ算法本身是一种贪婪算法，它通过分步的方法来求最短路径。
首先，初始产生源点到它自身的路径，其长度为零，然后在贪婪算法的每一步中，产生一个到达新的目的顶点的最短路径。
其算法描述如下（算法中以有向图表示网络结构）： 对于有向图Ｇ ＝（Ｖ，Ｅ），图中有ｎ个顶点，有ｅ条弧，其中Ｖ为顶点的集合，Ｅ为弧的集合，求源点ＶＳ到终点ＶＴ的最短路径。
（１） 用带权的邻接矩阵Ｌ来表示有向图，Ｌ（Ｘ，Ｙ）表示弧＜Ｘ，Ｙ＞的权值，若弧＜Ｘ，Ｙ＞不存在，则设Ｌ（Ｘ，Ｙ）＝∞；用Ｄ（Ｘ）表示源点ＶＳ到顶点Ｘ的距离，除源点ＶＳ的值为０外，其余各点设为∞；用Ｓ表示已找到的从源点ＶＳ出发的最短路径的顶点的集合，其初始状态为空集；用Ｖ－Ｓ表示未找到最短路径的顶点的集合； （２） 选择源点ＶＳ做标记，令Ｙ ＝ ＶＳ，Ｓ ＝ Ｓ ∪ ｛ＶＳ｝； （３） 对于Ｖ－Ｓ中各顶点， 若Ｄ（Ｘ） ＞ Ｄ（Ｙ） ＋ Ｌ（Ｙ，Ｘ），则修改Ｄ（Ｘ）为 Ｄ（Ｘ） ＝ Ｄ（Ｙ） ＋ Ｌ（Ｙ，Ｘ） 其中Ｙ是己确定作标记的点； （４） 选择Ｖｊ，使得Ｄ（ｊ） ＝ ｍｉｎ｛ Ｄ（ｉ） ｜ Ｖｉ ∈ Ｖ－Ｓ ｝ 若Ｄ（ｊ）为∞，则说明ＶＳ到Ｖ－Ｓ中各顶点都没有通路，算法终止；否则，Ｖｊ就是当前求得的一条从源点ＶＳ出发的最短路径的终点，对Ｖｊ做标记，令Ｙ ＝ Ｖｊ，并把Ｖｊ放入集合Ｓ中，即令Ｓ ＝ Ｓ ∪ ｛Ｖｊ｝； （５） 如果Ｙ等于ＶＴ，则说明已经找到从ＶＳ到ＶＴ的最短路径，算法终止；否则，转到３继续执行。
（一）实验目的本实验的目的是通过理解图的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。
（二）实验内容1、编写生成创建一个图存储全国铁路系统的数据结构；2、编写输出遍历图中所有城市枢纽的函数；3、编写实现任意两城市之间最短铁路路程的函数；4、编写实现输出这任意两城市铁路线最短距离以及沿途比经过的铁路站点的城市。
(三）实验要求1、掌握图型数据结构的机器内表示和存储；2、掌握图型结构之上的算法设计与实现；3、对迪杰斯特拉算和程序的时间复杂度、空间复杂度分析。
4、掌握最短路径算法思路和实现。
(四)实验设计思路实验中我采用邻接矩阵来创建和存储一个全铁路系统的有向图,并实现了对途中所有节点的遍历。
程序采用迪杰斯特拉(Dijkstra)算法，实现了对图中任意两城市之间的最短距离的求解，并编写输出最短路径和所有经过的城市名。
例如：输入北京到西安时，输出450km(四)程序清单#i n c l u d e<s t d i o.h>#i n c l u d e<s t d l i b.h>#i n c l u d e<s t r i n g.h>#d e f i n e I N F I N I T Y10000#d e f i n e m a x100#d e f i n e l e n20#d e f i n e N U L L0s t r u c t v e r t e x{i n t n u m;c h a rd a t a[le n];};s t r u c t g r a p h{i n t n,e;v e r t e x v e x s[m a x];i n t e d g e s[m a x][m a x];};v o i d c r e a t e g r a p h(g r a p h*g r a){i n t i,j,k,w;c h a r b[l e n],t[l e n];p r i n t f("请输入全国铁路枢纽城市个数:\n");s c a n f("%d",&g r a->n);p r i n t f("请输入全部枢纽城市之间的干线数:\n");s c a n f("%d",&g r a->e);f o r(i=0;i<g r a->n;i++){p r i n t f("请输入第%d个城市名称：\n",i+1);s c a n f("%s",g r a->v e x s[i].d a t a);g r a->v e x s[i].n u m=i;}f o r(i=0;i<g r a->n;i++)f o r(j=0;j<g r a->n;j++)g r a->e d g e s[i][j]=I N F I N I T Y;f o r(k=0;k<g r a->e;k++){p r i n t f("输入第%d条铁路干线的信息：\n",k+1);p r i n t f("起点站序号：\n");s c a n f("%s",b);p r i n t f("终点站序号：\n");s c a n f("%s",t);p r i n t f("起始站和终点站干线长度：");s c a n f("%d",&w);i=0;w h i l e(i<g r a->n&&s t r c m p(g r a->v e x s[i].d a t a,b)!=N U L L) i++;i f(i>=g r a->n){p r i n t f("输入起点的城市不正确！\n");e x i t(1);}j=0;w h i l e(j<g r a->n&&s t r c m p(g r a->v e x s[j].d a t a,t)!=N U L L) j++;i f(i>=g r a->n){p r i n t f("输入终点的城市不正确！\n");e x i t(2);}g r a->e d g e s[i][j]=w;}}v o i d d i s p l a y(g r a p h*g r a){i n t i,j,f l a g=0;d o u b le s u m=0;i f(!g r a->v e x s[0].d a t a)p r i n t f("没有铁路城市信息!请先创建铁路信息.\n");e l s e{p r i n t f("全国铁路枢纽城市的信息如下：\n");f o r(i=0;i<g r a->n;i++){f o r(j=0;j<g r a->n;j++)s u m+=g r a->e d g e s[i][j];i f(((i n t)s u m/g r a->n)>=I N F I N I T Y)f l a g=1;p r i n t f("城市名称\t序号\n");p r i n t f("%s\t\t%d\n",g r a->v e x s[i].d a t a,i);i f(f l a g)p r i n t f("\t该城市不可达其他城市.\n");e l s e{p r i n t f("\t\t可达以下城市：\n");p r i n t f("\t城市名称\t\t序号\t\t铁路线距离\n");f o r(j=0;j<g r a->n;j++){i f(g r a->e d g e s[i][j]<I N F I N I T Y)p r i n t f("\t%s\t\t\t%d\t\t\t%l d(K m)\n",g r a->v e x s[j].d a t a,g r a->v e x s[j].n u m,g r a->e d g e s[i][j]);}}f l a g=0;s u m=0;p r i n t f("\n");}}}v o i d s h o r t P a t h(g r a p h*g r a,i n t v0,i n t p[][m a x],i n t d[m a x]) {i n t v,w,i,j,m i n;i n t f i n a l[m a x];f o r(v=0;v<g r a->n;v++){f i n a l[v]=0;d[v]=g r a->e d g e s[v0][v];f o r(w=0;w<m a x;w++)p[v][w]=-1;i f(d[v]<I N F I N I T Y){p[v][0]=v0;p[v][1]=v;}}d[v0]=0;f i n a l[v0]=1;f o r(i=1;i<g r a->n;i++){m i n=I N F I N I T Y;f o r(w=0;w<g r a->n;w++){i f(!f i n a l[w]){i f(d[w]<m i n){v=w;m i n=d[w];}}}f i n a l[v]=1;f o r(w=0;w<g r a->n;w++){i f(!f i n a l[w]&&(m i n+g r a->e d g e s[v][w]<d[w])){d[w]=m i n+g r a->e d g e s[v][w];f o r(j=0;p[v][j]>-1&&j<g r a->n;j++){p[w][j]=p[v][j];}p[w][j]=w;}}}}v o i d f i n d p a t h(g r a p h*g r a){i n t i,j,v0,v e n d,f l a g1=0,f l a g2=0;i n t d[m a x],p[m a x][m a x];c h a r s c i t y[l e n],e c i t y[l e n];p r i n t f("输入铁路起始站城市名称：\n");s c a n f("%s",s c i t y);p r i n t f("输入铁路终止站城市名称：\n");s c a n f("%s",e c i t y);f o r(i=0;i<g r a->n;i++){i f(s t r c m p(g r a->v e x s[i].d a t a,s c i t y)==N U L L){v0=g r a->v e x s[i].n u m;f l a g1=1;}i f(s t r c m p(g r a->v e x s[i].d a t a,e c i t y)==N U L L){v e n d=g r a->v e x s[i].n u m;f l a g2=1;}}i f(f l a g1==N U L L){p r i n t f("输入的起始站错误！");e x i t(1);}i f(f l a g2==N U L L){p r i n t f("输入的终止站错误！");e x i t(2);}e l s e{s h o r t P a t h(g r a,v0,p,d);f o r(i=0;i<g r a->n;i++){i f(i==v e n d){i f(d[i]>=I N F I N I T Y)p r i n t f("从%s到%s不可达！\n",g r a->v e x s[v0].d a t a,g r a->v e x s[v e n d].d a t a);e l s e{p r i n t f("从%s城市出发到%s城市最短路径经过的城市为:\n",g r a->v e x s[v0].d a t a,g r a->v e x s[v e n d].d a t a);i f(p[i][v0]>-1){f o r(j=0;p[i][j]!=-1;j++){i f(j!=0)p r i n t f("->");p r i n t f("%5s",g r a->v e x s[p[i][j]].d a t a);}p r i n t f("\n");}p r i n t f("最短路径长为:%l d(k m)\n",d[i]);p r i n t f("\n");}}}}}i n t m a i n(){g r a p h g r a;c h a r c h;d o{p r i n t f("┌———————————————————─┐\n");p r i n t f("│┈┈☆☆欢迎使用铁路查询系统☆☆┈┈│\n");p r i n t f("│请选择下面操作│\n");p r i n t f("│ 1.创建铁路系统2.查看全部铁路信息│\n");p r i n t f("│ 3.任意两城市铁路信息查询4.退出铁路系统│\n");p r i n t f("└——————————————————─┘\n\t");s c a n f("%c",&c h);s w i t c h(c h){c a s e'1':c r e a t e g r a p h(&g r a);g e t c h a r();b r e a k;c a s e'2':d i s p l a y(&g r a);ge t c h a r();b r e a k;c a s e'3':f i n d p a t h(&g r a);g e t ch a r();b r e a k;c a s e'4':p r i n t f("┈┈┈☆☆欢迎下次使用铁路信息系统☆☆┈┈┈┈┈\n");b r e a k;}}w h i l e(c h!='4');r e t u r n0;}（五）实验结果1创建铁路系统：2.查询全部铁路信息：3.任意两城市信息查询：（六）实验思考实验采用邻接表存储有向图，怎么具体实现迪杰斯特拉算法？先定义一个数组对每个顶点到其余城市可达距离，其余和邻接矩阵迪杰斯特拉算法相同。
最短路径问题介绍全文共四篇示例，供读者参考第一篇示例：最短路径问题是指在一个带有边权的图中，寻找连接图中两个特定节点的最短路径的问题。
在实际生活中，最短路径问题广泛应用于交通运输、通信网络、物流配送等领域。
通过解决最短路径问题，可以使得资源的利用更加高效，节约时间和成本，提高运输效率，并且在紧急情况下可以迅速找到应急通道。
最短路径问题属于图论中的基础问题，通常通过图的表示方法可以简单地描述出这样一个问题。
图是由节点和边组成的集合，节点表示不同的位置或者对象，边表示节点之间的连接关系。
在最短路径问题中，每条边都有一个权重或者距离，表示从一个节点到另一个节点移动的代价。
最短路径即是在图中找到一条路径，使得该路径上的边权和最小。
在解决最短路径问题的过程中，存在着多种算法可以应用。
最著名的算法之一是Dijkstra算法，该算法由荷兰计算机科学家Edsger W. Dijkstra于1956年提出。
Dijkstra算法是一种贪心算法，用于解决单源最短路径问题，即从一个给定的起点到图中所有其他节点的最短路径。
该算法通过维护一个距离数组和一个集合来不断更新节点之间的最短距离，直到找到目标节点为止。
除了Dijkstra算法和Floyd-Warshall算法外，还有一些其他与最短路径问题相关的算法和技术。
例如A*算法是一种启发式搜索算法，结合了BFS和Dijkstra算法的特点，对图中的节点进行评估和排序，以加速搜索过程。
Bellman-Ford算法是一种解决含有负权边的最短路径问题的算法，通过多次迭代来找到最短路径。
一些基于图神经网络的深度学习方法也被应用于最短路径问题的解决中，可以获得更快速和精确的路径搜索结果。
在实际应用中，最短路径问题可以通过计算机程序来实现，利用各种算法和数据结构来求解。
利用图的邻接矩阵或者邻接表来表示图的连接关系，再结合Dijkstra或者Floyd-Warshall算法来计算最短路径。
邻接矩阵求最短路径
在图论中，求最短路径是一个非常重要的问题。
邻接矩阵是一种表示图的方式，它可以用矩阵的形式存储每个节点之间的连接关系和权重。
在邻接矩阵中，如果节点i和节点j之间存在一条边，则邻接矩阵的第i行第j列的元素为该边的权重；否则，该元素为0。
求最短路径的基本思想是从起点开始，依次遍历每个节点，并选择到达该节点的所有边中权重最小的边进行转移，直到到达终点为止。
在邻接矩阵中，我们可以使用动态规划的方法来实现这个算法。
具体来说，我们可以定义一个长度为n的数组dist，其中dist[i]表示从起点到节点i的最短路径长度。
初始时，dist[0]的值为0，其他元素的值均为无穷大。
然后，我们遍历从起点到每个节点的所有边，并更新dist数组的值。
对于每条边(i, j)，如果dist[i] + weight(i, j) < dist[j]，则更新dist[j]的值为dist[i] + weight(i, j)。
这样，当遍历完所有的边后，dist数组中的最小值即为从起点到终点的最短路径长度。
在实现时，我们还需要记录每个节点到达的最短路径所经过的节点。
这个信息可以用一个长度为n的数组prev来记录。
对于每个节点i，如果我们找到了从起点到节点i的最短路径，那么prev[i]的值就是该路径上节点i的前一个节点。
这个信息可以帮助我们在最后一步中反向追踪出最短路径。
在时间复杂度方面，由于我们只需要遍历一次所有的边，所以算法的时间复杂度为O(n^2)。
其中n为节点的数量。
数据结构上机报告（2) 姓名：张可心学号：14030188030 班级：1403018一、题目描述一个图的存储矩阵如下所示（顶点分别是0、1、2、3、4、5）：0，12，18，∞，17，∞12, 0，10，3，∞，518，10，0，∞，21，11∞，3，∞，0，∞，817，∞，21，∞，0，16∞，5，11，8，16，0试用邻接矩阵存储法和Floyd算法求解任意两个顶点的最短路径。
输入：输入数据第一行为1个正整：顶点个数n(顶点将分别按0，1，…，n-1进行编号)。
后面有n+1行，前n行都有n个整数（第i行第j个数表示顶点i-1和顶点j-1之间的边长，用10000来表示两个顶点之间无边）；第n+1行输入一对顶点x和y输出：x和y顶点的最短路径长度和最短路径(路径换行输出，只输出顶点编号序列)。
示例输入（1）：60 12 18 10000 17 1000012 0 10 3 10000 518 10 0 10000 21 1110000 3 10000 0 10000 817 10000 21 10000 0 1610000 5 11 8 16 00 1示例输出（1）：1201示例输入（2）：60 12 18 10000 17 1000012 0 10 3 10000 518 10 0 10000 21 1110000 3 10000 0 10000 817 10000 21 10000 0 1610000 5 11 8 16 02 3示例输出（2）：13213示例输入（3）：60 12 18 10000 17 1000012 0 10 3 10000 518 10 0 10000 21 1110000 3 10000 0 10000 817 10000 21 10000 0 1610000 5 11 8 16 01 4示例输出（3）：21154示例输入（in和out文件的内容）：60 12 18 10000 17 1000012 0 10 3 10000 518 10 0 10000 21 1110000 3 10000 0 10000 817 10000 21 10000 0 1610000 5 11 8 16 03 4示例输出：24354二、解题思路先用邻接矩阵存储法构建矩阵输入，分别输入顶点数，路径长度矩阵，邻接矩阵，再通过Floyd算法求解任意两个顶点的最短路径，具体代码如下。
习题7 图单项选择题1．在一个图中，所有顶点的度数之和等于所有边数的____倍。
A. 1/2B. 1C. 2D. 42．任何一个无向连通图的最小生成树。
A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。
A. 1/2B. 1C. 2D. 44．一个有n个顶点的无向图最多有____条边。
A. nB. n(n-1)C. n(n-1)/2D. 2n5．具有4个顶点的无向完全图有____条边。
A. 6B. 12C. 16D. 206．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。
A. 5B. 6C. 7D. 87．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。
A. nB. n+1C. n-1D. n/28．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。
A. nB. (n-1)2C. n-1D. n29．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。
①A. n B. n+1 C. n-1 D. n+e② A. e/2 B. e D. n+e10．已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②__。
① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b图一个无向图11．已知一有向图的邻接表存储结构如图所示。
⑴根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。
A. v1,v2,v3,v5,v4B. v1,v2,v3,v4,v5C. v1,v3,v4,v5,v2D. v1,v4,v3,v5,v2⑵根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。
实现图的最短路径算法（Python）图的最短路径算法是解决图中两个节点之间最短路径问题的方法。
在图中，节点之间可以通过边相连，并且每条边都有一个权重或距离值。
最短路径算法可以找到从起始节点到目标节点的最短路径，并计算出该路径上所有边权重的总和。
在实现图的最短路径算法之前，我们首先需要建立图的数据结构。
图可以通过邻接矩阵或邻接表来表示。
邻接矩阵是一个二维矩阵，其中矩阵的行和列代表图中的节点，矩阵中的元素表示节点之间的边的权重。
邻接表是一个字典，其中每个节点都与它的邻居节点列表相关联，列表中的元素表示节点之间的边的权重。
在Python中，我们可以使用字典和列表来实现图的邻接表表示。
首先，我们创建一个Graph类来表示图，并定义一些必要的方法。
以下是一个图类的示例实现：```pythonclass Graph:def __init__(self):self.nodes = set()self.edges = {}def add_node(self, node):self.nodes.add(node)def add_edge(self, from_node, to_node, weight):if from_node not in self.edges:self.edges[from_node] = {}self.edges[from_node][to_node] = weightdef get_neighbors(self, node):return self.edges[node]```在Graph类中，我们使用一个nodes集合来存储图中的节点，并使用一个edges字典来存储从一个节点到其他节点的边的权重。
add_node方法用于添加节点到图中，add_edge方法用于添加边的权重，get_neighbors方法用于获取一个节点的所有邻居节点及对应的边的权重。
接下来，我们可以通过实现最短路径算法来找到从起始节点到目标节点的最短路径。
数据结构课程设计题目名称：最短路径计算机科学与技术学院一、需求分析(1)题目：最短路径实现图的输入，选择合适的结构表示图，在此基础上实现求解最短路径的算法，可以从任意一点求最短路径，学生必须准备多组测试数据，并设计清晰易懂的输入输出界面，要求：如何用多种数据结构来求解问题。
同时要求实现对应数据结构的所有基本操作。
（2）程序的输入与输出:要求用多种数据结构求解问题，也就是要用邻接表与邻接矩阵实现最短路径的算法，需要有多组输入输出，(a)输入的形式和输入值的范围：输入的形式为整型1.先输入共需要创建几次图2.再分别输入边数和顶点数（范围：1~100）3.输入1和2选择是否为有向图图（1为有向，2为无向）4.对应每条边输入起点和终点下标，以及对这条边的权值（最大的权值为100）。
5.输入在邻接表的基础上输入深度与广度优先搜索的起点6.我们输入求各种最短路径起点和终点(b)输出的形式；1.输出所建立的邻接表（表结点后面的括号是头结点与表结点的权值）2.输出DFS和BFS的结果3.输出该图不带权值的最短路径与路径4.接下来输入起点和终点，求带权值的最短路径也就是Dijstra算法，输出长度并给出路径5.前面都是用邻接表实现的各种算法，接下来的Floyd算法就用矩阵实现，于是直接邻接表转矩阵输出6.用Floyd算法求出图的多源最短路径，给出起点终点输出最短路径长度，接着便到了第二次创建图，直至循环结束。
（3）程序的功能:求给出带权图的任意两点，输出最短路径长度并给出其最短路径所经过的顶点。
在实际应用中可以将交通网络化成带权的图，图中顶点表示城市，边代表城市之间的公路，边上的权值表示公路的长度。
这样可以发现两个地方之间有无公路可连，在几条公路可通的情况下，可以找到那条路径最短。
也就是现在地图app中的功能。
（4）测试数据:包括正确的输入及其输出结果和含有错误的输入及其输出结果。
在有向图中输入错误的数据（顶点与顶点方向相反），会输出逆向信息。
