弗洛伊德算法求最短路径 输出路径
弗洛伊德算法其实比较好理解

这里我用邻接矩阵的储存方法来写
一.算法思想
1.1

如果我们要用邻接矩阵来写代码的话，就要储存他的权值信息

这里我们用map[][]这个二维数组来储存

其次要输出他的最短路径

就用path[][]来储存
    int map[100][100];
	int path[100][100];

1.2

初始化这个储存权值邻接矩阵

由于是无环图，自己到自己是 0

剩下的边的权值我们赋值为MAX
for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(i==j)
                map[i][j]=0;
            else
                map[i][j]=max;

1.3

读入边的信息

如果两个结点i，j之间有权值，就把他赋值给map[i][j]

并且这个时候将j赋值给path[i][j]
	cout<<"输入点1到点2的距离"<<endl; 
    for(int i=1; i<=m; i++)
    {
        cin>>t1>>t2>>t3;
        map[t1][t2]=t3;
        map[t2][t1]=t3;
        path[t1][t2]=t2;
    }

这个路径的赋值如果在后面有更优解

将会更新这个值，如果没有，那说明i直接到j就是最短的
1.4 核心算法

这个核心算法使用一个三重循环来一个一个找最优解

第一重循环控制中转结点k

第二重控制起始结点i

第三重控制终止结点j
如果我们发现i->k->j的路径小于i->j的

那我们就更新路径，将path[i][j]=path[i][k]

同时权值邻接矩阵更新`map[i][j]=map[i][k]+map[k][j]
for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(map[i][k]+map[k][j]<map[i][j])
                {
                	 map[i][j]=map[i][k]+map[k][j];
                	 path[i][j]=path[i][k];
				}

1.5

输出最短路径的值
for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
            cout<<map[i][j]<<" ";
            cout<<endl;
    }

1.6

输出最短路径

这里我们要输入两个结点v1 v2

最后输出的就是v1到v2的最短路径

仔细想想我们的path[v1][v2]储存的是v1 v2的第一个中转节点z的信息

输出z后，path[z][v2]储存的是z到v2的第一个中转结点

一个一个输出这些中转结点

以此类推，直到z为v2的时候，这就是v1到v2的最短路径
int v1,v2,z;
    cout<<"输入两个点，输出之间路径"<<endl; 
    cin>>v1>>v2;
    z=path[v1][v2];
    cout<<v1;
    while(z!=v2)
    {
    	cout<<"->"<<z;
    	z=path[z][v2];
	}
	cout<<"->"<<v2;

二.测试数据




这里的最短距离我直接的输出距离矩阵了

如果要输出更方便阅读的形式

也可以在输出那块把代码改一下，可以cout<<"v1到v2的距离为：<<map[v1][v2]<<endl

我就不多写了
##测试数据

1 2 2

1 3 1

2 3 5

2 4 4

3 4 5

4 5 6
三.源代码
#include<iostream>
using namespace std;
#define max 99999

void fuluoyide(int n,int m)
{
	int map[100][100],t1,t2,t3;
	int path[100][100];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(i==j)
                map[i][j]=0;
            else
                map[i][j]=max;
    //读入边
	cout<<"输入点1到点2的距离"<<endl; 
    for(int i=1; i<=m; i++)
    {
        cin>>t1>>t2>>t3;
        map[t1][t2]=t3;
        map[t2][t1]=t3;
        path[t1][t2]=t2;
    }
    //弗洛伊德(Floyd)核心语句
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(map[i][k]+map[k][j]<map[i][j])
                {
                	 map[i][j]=map[i][k]+map[k][j];
                	 path[i][j]=path[i][k];
				}
                   
    cout<<endl<<"最短距离矩阵为："<<endl; 
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
            cout<<map[i][j]<<" ";
            cout<<endl;
    }
    
    int v1,v2,z;
    cout<<"输入两个点，输出之间路径"<<endl; 
    cin>>v1>>v2;
    z=path[v1][v2];
    cout<<v1;
    while(z!=v2)
    {
    	cout<<"->"<<z;
    	z=path[z][v2];
	}
	cout<<"->"<<v2;  
} 

int main()
{
	cout<<"输入顶点数，边数"<<endl; 
	int n,m;
    cin>>n>>m;//n表示顶点个数，m表示边的条数
    cout<<endl;
    fuluoyide(n,m);
}


总体来说 弗洛伊德算法的思想不是很难懂，有一点点暴力求值的感觉，就硬算

我还写了一篇 dijkstra 求最短路径的算法，也可以看看

如果帮助到你了，点个赞吧

某个源点到其余各顶点的最短路径 

这个算法最开始心里怕怕的，不知道为什么，花了好长时间弄懂了，也写了一遍，又遇到时还是出错了，今天再次写它，心里没那么怕了，耐心研究，懂了之后会好开心的，哈哈

Dijkstra算法：

图G     

如图：若要求从顶点1到其余各顶点的最短路径，该咋求；

迪杰斯特拉提出“按最短路径长度递增的次序”产生最短路径。

首先，在所有的这些最短路径中，长度最短的这条路径必定只有一条弧，且它的权值是从源点出发的所有弧上权的最小值，例如：在图G中，从源点1出发有3条弧，其中以弧（1，2）的权值为最小，因此，（1，2）不仅是1到2的一条最短路径，并且它可能是源点到其它各个终点的最短路径中的一条子路径。

其次，第二条长度次短的最短路径只可能有两种情况：①它或者只含一条从源点出发的弧且弧上的权值大于已求得最短路径的那条弧的权值，但小于其他从源点出发的弧上的权值②它或者是一条只经过已求得最短路径的顶点的路径。

例如图G中，从1到其他各点。过程中，用d[i]保存从1到i的的最短路径（过程会变化），初值为：若源点到该源点有弧，则为权值，否则初始化为无穷大，每求得一条到达某个终点i的最短路径，就继续检查是否存在以此路径为子路径的到达其他点的最短路径，若存在，判断其长度是否比当前求得的路径长度短，若短，就更新为更短的长度。 

如图G中，求得到2的最短路径d[2]为10，就把d[2]作为与2相连的到其他点的子路径继续检查，得到到3的最短路径为d[2]+50=60

过程： 

（1）.令S={1}，S集合中表示已经找到最短路径的结点，开始时1为源点，并设定d[i]的初始值为：d[i]=(1,i), 

（2）.求出到j点的最短路径，j点为不在S集合中的某点 

d[j]=min{d[i]} 

（3）.判断所有没在S集合中的顶点k，若d[k]>d[j]+(j,k)则修改d[k]的值为： 

d[k]=d[j]+(j,k) 

（4）.重复（2）.（3）操作共n-1次，每次操作，在（2）得到一个到  

某点的最短路径。

有向图求最短路径



#include<stdio.h>
#include<string.h> 
#include<stdlib.h>
#define max 900000000

//有向图 
int main(){
    int n,m,a,b,v,i,j,min,k;
    scanf("%d%d",&n,&m);//输入n个顶点，m条边 
    int g[n+1][n+1],d[n+1],vis[n+1];//g[i][j]表示i到j的边的权值,vis[i]表示到此顶点的最短路是否已经找到，d[i]当前源点到i顶点的最短路径 
    memset(vis,0,sizeof(vis));
    for(i=0;i<=n;i++){ 
        for(j=0;j<=n;j++){
            g[i][j]=max;
        }
        d[i]=max;   
    }
    for(i=0;i<m;i++){//i到j的边权值储存到g邻接矩阵中,i点到j点无直接相连的边时，g[i][j]=max  
        scanf("%d%d%d",&a,&b,&v);
        g[a][b]=v;
    }
    for(i=2;i<=n;i++){
            d[i]=g[1][i]; //初始化源点到i点边权值，之后过程中会发生变化 
    }
    vis[1]=1;
    for(i=2;i<=n;i++){//共循环n-1次，每循环一次，确定一条最短路，再次循环时这条路就不用考虑了，去寻找下一条最短路 
        min=max;
        for(j=2;j<=n;j++){//寻找下一条当前最短路 
           if(d[j]<min&&vis[j]==0){
             min=d[j];
             k=j;
           }    
        }
        vis[k]=1;//找到了，到k点的路是当前最短路，标记它，根据它寻找下一条最短路 
        for(j=2;j<=n;j++){
            if(d[j]>d[k]+g[k][j]&&vis[j]==0){//经过此k点到达j点的路径是否小于其他到达j点的路径 
                d[j]=d[k]+g[k][j];
            }
        }
    }   
    for(i=2;i<=n;i++){//输出到达个点的最短路径 
        printf("%d\n",d[i]);
    }
    return 0;
} 

无向图求最短路径 

无向图也是相同思路：在构造邻接矩阵时考虑对称就行。

无向图求最短路径且有路径输出 

在求最短路的过程中，最短路①它或者是从源点出发的弧②它或者是一条经过已到其他最短路径的顶点的路径。

建立一个新的结构体类型path，该类型变量d表示到达某点的最短路径距离 ，该类型变量pre表示该最短路径是经过哪个点传过来的

#include<stdio.h>
#include<string.h> 
#include<stdlib.h>
#define max 900000000

typedef struct{ 
    int d;//到达某点的最短路径距离 
    int pre;//该最短路径是经过哪个点传过来的，源点或其他某个点 
}path; 

//有向图 
int main(){
    int n,m,a,b,v,i,j,min,k,from;
    scanf("%d%d",&n,&m);//输入n个顶点，m条边 
    int g[n+1][n+1],vis[n+1];//g[i][j]表示i到j的边的权值,vis[i]表示到此顶点的最短路是否已经找到，d[i]当前源点到i顶点的最短路径 
    path to[n+1];//记录当前到某个点的最短路径以及从哪个点传过来的 
    memset(vis,0,sizeof(vis));
    for(i=0;i<=n;i++){ 
        for(j=0;j<=n;j++){
            g[i][j]=max;
        }
        to[i].d=max;    
    }
    for(i=0;i<m;i++){//i到j的边权值储存到g数组中,i点到j点无直接相连的边时，g[i][j]=max  
        scanf("%d%d%d",&a,&b,&v);
        g[a][b]=v;
        g[b][a]=v;
    }
    for(i=2;i<=n;i++){
            to[i].d=g[1][i]; //初始化源点到i点边权值，之后过程中会发生变化 
            if(g[1][i]!=max){
              to[i].pre=1;  
            } 
    }
    vis[1]=1;
    for(i=2;i<=n;i++){//共循环n-1次，每循环一次，确定一条最短路，再次循环时这条路就不用考虑了，去寻找下一条最短路 
        min=max;
        for(j=2;j<=n;j++){//寻找下一条当前最短路 
           if(to[j].d<min&&vis[j]==0){
             min=to[j].d;
             k=j;
           }    
        }
        vis[k]=1;//找到了，到k点的路是当前最短路，标记它，根据它寻找下一条最短路 
        for(j=2;j<=n;j++){
            if(to[j].d>to[k].d+g[k][j]&&vis[j]==0){//经过此k点到达j点的路径是否小于其他到达j点的路径 
                to[j].d=to[k].d+g[k][j];
                to[j].pre=k;//改变j点是谁传来的，现在到j点的最短路径是经过k点的，由j点传来  
            }
        }
    }   
    for(i=2;i<=n;i++){//输出到达个点的最短路径 
        printf("%d ",to[i].d);
        printf("%d ",i);
        j=i;
        while(j!=1){
            j=to[j].pre;
            printf("%d ",j);
        }
        printf("\n");
    }
    return 0;
} 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define inf 0x3f3f3f3f
int dis[200];
int vis[200];
int map[200][200];
struct mmm
{
    int x;
    int y;
    int v;
}xxx[200];
void dijkstra(int S,int N)   //S表示start,E表示终点
{
    int i,j;
    dis[S] = 0;              //初始化起始点
    vis[S] = 1;
    for(i=1;i<=N;i++)
    {
        if(vis[i]==0)        //避免自己dis[S]被赋值。
        dis[i]=map[S][i];    //算出所有直达
    }
    for(i=1;i<=N;i++)
    {
      int minn = inf, mini = S;  //minn在新的开始又变成了无穷大
      for(j=1;j<=N;j++)
      {
        if(vis[j]==0&&minn>dis[j])
        {
            minn=dis[j];
            mini=j;
        }
      }                          //第一个for每能定一个最短。
      vis[mini]=1;              //做标记,dis[mini]就定住哪个已经是最短了。
      for(j=1;j<=N;j++)
      {
        if(vis[j]==0)
        {
            if(dis[j]>dis[mini]+map[mini][j])    //第二个for是算转达。
            {                                    // 第n个最短，在最后一次之前已经在不断更新的，所以，每次都是最短比最新的，取最短。


                    dis[j]=dis[mini]+map[mini][j];


            }
        }
      }
    }
}
int main()
{
   int n,m;
   int i,j;
   struct mmm t;
   scanf("%d%d",&n,&m);
   for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
		 {
            if(i==j)
			map[i][j]=0;
            else map[i][j]=inf;
         }
    }
   while(m--)
   {
       int i,j,val;
       scanf("%d%d%d",&i,&j,&val);
       map[i][j]=val;
   }
   dijkstra(1,n);
   for(i=1;i<=n;i++)
   {
       xxx[i].v=dis[i];
       xxx[i].y=i;
   }
  for(j=1;j<n;j++)
    for(i=1;i<=n-j;i++)
      if(xxx[i].v>xxx[i+1].v)
  {
      t=xxx[i];
      xxx[i]=xxx[i+1];
      xxx[i+1]=t;
  }
   for(i=2;i<=n;i++)
   {
      if(dis[i]==inf)
      printf("1 %d -1\n",xxx[i].y);
      else
      printf("1 %d %d\n",xxx[i].y,xxx[i].v);
   }
    return 0;
}

实验说明
[实验目的]

掌握图的存储方法和最短路径算法。

[实验内容]

设计一个校园导游程序，为来访的客人提供各种信息查询服务。测试数据根据实际情况指定。提示：一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向图。顶点和边均含有相关信息。

[实验要求]

(1)设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。

(2)为来访客人提供图中任意景点相关信息的查询。

(3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
迪杰特斯拉算法
对于如图所示的平面图，首先写出它的邻接矩阵



邻接矩阵arcs[11][11]（∞代表两个顶点间没有边，数字为两顶点间边的权值）



假设从v0出发，找vo到其余十一个顶点的最短路径，那么数组D[ ] =arcs[0][ ]。数组D是一个辅助向量，它的每个分量D[i]表示当前所找到的从始点v0到每个终点vk的最短路径。刚开始执行迪杰斯特拉时，初始化数组D[ ] = {∞ , 2,  ∞ , ∞,  ∞ ,  6,  ∞,  ∞ , ∞ , ∞ , ∞,    ∞}，从D中选取权值最小的点，作为第一条最短路径的终点，显然，此时应该选取点v1，把v1放入数组S中，表示v1这个点已经选取过了，避免重复选取同一个点作为最短路径的终点。为了程序描述起来方便，把每次选取的最短路径的终点都保存在变量min中，显然，此时min = v1，S = {v1}，D[ ] = {∞ , 2,  ∞ , ∞,  ∞ ,  6,  ∞,  ∞ , ∞ , ∞ , ∞,    ∞}，D中把2斜体加粗说明下次选权值最小的点时就不能再选择边（v0，v1）了。

按照迪杰斯特拉算法的核心思想，下一条最短路径的终点vj要么与v0直接相连，此时最短路径为（v0，vk），要么与min直接相连，此时最短路径为（v0，min）∪（min，vk）。现在需要做的工作就是判断D[k]与D[min] + arcs[min][k]的大小。若D[min] + arcs[min][k]小于D[k]，说明从始点v0到到vk经过顶点Vmin的路径要短于直接从V0到Vk的路径。那么此时需要执行语句D[k] = D[min] + arcs[min][k]，对最短路径进行更新。k取遍所有的顶点为一次循环（始点V0除外，否则可能会形成一个包含顶点V0的回路）。
第一次循环:

由于此时min = v1，所以比较D[1] + arcs[1][k]和D[k]的大小关系，若D[1] + arcs[1][k]小于D[k]，说明从始点v0到终点vk经过顶点v1的路径要短于直接从V0到Vk的路径。那么此时需要执行语句D[k] = D[1] + arcs[1][k]，对最短路径进行更新。循环结束之后，数组D = {∞ , 2,  6 , ∞,  ∞ ,  6,  ∞,  ∞ , ∞ , ∞ , ∞,    ∞}，现在需要从D中选取权值最小的点作为最短路径的终点，可以看到，D中有两个6，这种情况下选哪一个都可以，取决于你的选择函数是怎么写的，我的选择函数选的是第一个6，所以此时min = v2，S = {v1，v2}， D = {∞ , 2,  6 , ∞,  ∞ ,  6,  ∞,  ∞ , ∞ , ∞ , ∞,    ∞}，进入下一次循环。

第二次循环:

过程和第一次循环一样，只不过是现在需要比较D[2] + arcs[2][k]和D[k]的大小，循环结束之后，数组D = {∞ , 2,  6 , 9,  8 ,  6,  9,  ∞ , ∞ , ∞ , ∞,    ∞}，从D中选择最小值，min = v5，S = {v1，v2，v5}，D = {∞ , 2,  6 , 9,  8 ,  6,  9,  ∞ , ∞ , ∞ , ∞,    ∞}。

第三次循环:

比较D[5] + arcs[5][k]和D[k]的大小，循环结束之后，数组D = {∞ , 2,  6 , 9,  8 ,  6,  9,  ∞ , 13 , ∞ , ∞,    ∞}，从D中选择最小值，min = v4，S = {v1，v2，v5，v4}，D = {∞ , 2,  6 , 9,  8 ,  6,  9,  ∞ , 13 , ∞ , ∞,    ∞}

第四次循环:

比较D[4] + arcs[4][k]和D[k]的大小，循环结束之后，数组D = {∞ , 2,  6 , 9,  8 ,  6,  9,  10 , 13 , ∞ , ∞,    ∞}，从D中选择最小值，min = v3，S = {v1，v2，v5，v4，v3}，D = {∞ , 2,  6 , 9,  8 ,  6,  9,  10 , 13 , ∞ , ∞,    ∞}

第五次循环:

比较D[3] + arcs[3][k]和D[k]的大小，循环结束之后，数组D = {∞ , 2,  6 , 9,  8 ,  6,  9,  10 , 13 , ∞ , ∞,    ∞}，从D中选择最小值，min = v6，S = {v1，v2，v5，v4，v3，v6}，D = {∞ , 2,  6 , 9,  8 ,  6,  9,  10 , 13 , ∞ , ∞,    ∞}

第六次循环:

比较D[6] + arcs[6][k]和D[k]的大小，循环结束之后，数组D = {∞ , 2,  6 , 9,  8 ,  6,  9,  10 , 13 , 15 , ∞,    ∞}，从D中选择最小值，min = v7，S = {v1，v2，v5，v4，v3，v6，v7}，D = {∞ , 2,  6 , 9,  8 ,  6,  9,  10, 13 , 15 , ∞,    ∞}

第七次循环:

比较D[7] + arcs[7][k]和D[k]的大小，循环结束之后，数组D = {∞ , 2,  6 , 9,  8 ,  6,  9,  10 , 13 , 15 , ∞,    ∞}，从D中选择最小值，min = v8，S = {v1，v2，v5，v4，v3，v6，v7，v8}，D = {∞ , 2,  6 , 9,  8 ,  6,  9,  10, 13 , 15 , ∞,    ∞}

第八次循环:

比较D[8] + arcs[8][k]和D[k]的大小，循环结束之后，数组D = {∞ , 2,  6 , 9,  8 ,  6,  9,  10 , 13 , 15 , ∞,    15}，从D中选择最小值，min = v9，S = {v1，v2，v5，v4，v3，v6，v7，v8，v9}，D = {∞ , 2,  6 , 9,  8 ,  6,  9,  10, 13 , 15 , ∞,    15}

第九次循环:

比较D[9] + arcs[9][k]和D[k]的大小，循环结束之后，数组D = {∞ , 2,  6 , 9,  8 ,  6,  9,  10 , 13 , 15 , 16,    15}，从D中选择最小值，min = v11，S = {v1，v2，v5，v4，v3，v6，v7，v8，v9，v11}，D = {∞ , 2,  6 , 9,  8 ,  6,  9,  10, 13 , 15 , 16,    15}

第10次循环:

比较D[11] + arcs[11][k]和D[k]的大小，循环结束之后，数组D = {∞ , 2,  6 , 9,  8 ,  6,  9,  10, 13 , 15 , 16,    15}，从D中选择最小值，min = v10，S  = {v1，v2，v5，v4，v3，v6，v7，v8，v9，v11，v10}，D = {∞ , 2,  6 , 9,  8 ,  6,  9,  10, 13 , 15 , 16,    15}

迪杰斯特拉算法结束！
程序分析
景点为自定义的结构体类型，包括景点名称，代码，景点介绍三部分。
struct Scenic_sports {
	char name[15];
	int code;
	char info[100];
};

用结构体数组存放全部的12个景点，每个景点相当于无向图的一个顶点，景点的代码是数组的下标，同时也是该景点对应顶点的编号。在主函数中初始化景点数组。

当用户选择寻找景点间最短路径功能时，调用get_shortest_path函数，在此函数中，对景点的邻接矩阵arcs进行初始化。定义一个名为predecessor的数组，用于存储最短路径上每个顶点的前驱，这样做可以很方便的输出找到的最短路径。举个例子，比如说在某次循环中，D[4] + arcs[4][7] < D[7],成立，那么下一步就要执行D[7] = D[4] + arcs[4][7]，相当于是把v7这个点加入到当前找到的最短路径中，再下一步执行predecessor[7] = 4,这样就建立起了v7的前驱。当然，如果后续循环中有D[7] + arcs[7][k] < D[k]成立，那么v7就会成为vk的前驱，即执行语句predecessor[k] = 7。

我们可以通过访问v7的前驱找到v4，而v4的前驱有两种可能，如果v4的前驱不是起始点，那么v4一定是通过D[min] + arcs[min][4] < D[4]条件成立才加入到最短路径中的。也就是说v4的前驱也已经存放在predecessor[4]中了。如果v4的前驱是起始点，我们是没法通过上面的条件语句建立v4的前驱的，但我们可以通过另一种方法来解决这个问题，开始时，把所有顶点的前驱都初始化成起始点即可完美解决。

注意:假如要查询从景点2到景点9的最短路径，始点设为景点2，根据前驱数组输出图中经过的景点时，只能先去找景点9的前驱，然后再一直往前索引，直到索引到景点2，这样输出的路径是逆序的，也就是说输出的是从景点9到景点2的路径。我们换一种思路，当用户要查询景点2到景点9的路径时，我们把始点设为景点9，这样最终输出的路径就是景点2到景点9的路径。
源码

#include "pch.h"   
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 12
#define MAX_NUM 10000000
//景点结构体
struct Scenic_sports {
	char name[15];
	int code;
	char info[100];
};
//查询景点信息
void get_info(Scenic_sports position[]) {
	printf("请输入要查询的景点代号：");
	int code;
	scanf("%d", &code);
	printf("%s", position[code].info);
}
//判断当前顶点是否在数组S中，也就是说是否已经被选择过
bool has_selected(int S[], int i, int k) {
	for (int j = 0; j < k; j++)
		if (i == S[j])
			return true;
	return false;
}
//从数组D中选取最小值
int search_min(int D[], int S[], int k) {	//k为数组S中元素的个数，也就是说现在已经选了k条最短路径
	int min = -1;	//若为非连通图，则返回-1
	int m = MAX_NUM;
	for (int i = 0; i < MAX_SIZE; i++) 
		if (!has_selected(S, i, k) && (D[i] < m)) {
			min = i;
			m = D[i];
		}
	
	return min;
}
//寻找最短路径
void get_shortest_path(Scenic_sports position[]) {
	int arcs[MAX_SIZE][MAX_SIZE];	//邻接矩阵，里面存放着边的权值
//初始化邻接矩阵
	for (int i = 0; i < MAX_SIZE; i++)
		for (int j = 0; j < MAX_SIZE; j++)
			arcs[i][j] = MAX_NUM;
	arcs[0][1] = arcs[1][0] = 2;
	arcs[1][2] = arcs[2][1] = 4;
	arcs[2][3] = arcs[3][2] = 3;
	arcs[2][6] = arcs[6][2] = 3;
	arcs[2][4] = arcs[4][2] = 2;
	arcs[0][5] = arcs[5][0] = 6;
	arcs[4][5] = arcs[5][4] = 3;
	arcs[4][7] = arcs[7][4] = 2;
	arcs[5][8] = arcs[8][5] = 7;
	arcs[7][8] = arcs[8][7] = 5;
	arcs[6][9] = arcs[9][6] = 6;
	arcs[9][10] = arcs[10][9] = 1;
	arcs[10][11] = arcs[11][10] = 1;
	arcs[11][8] = arcs[8][11] = 2;

	int min = 0;	//当前寻找到的最短路径的终点
	int adr1, adr2;		//查询从景点adr1到景点adr2的最短路径
	int D[MAX_SIZE] = { 0 };	//它的每个分量D[i]表示当前所找到的从始点adr1到每个终点vi的最短路径的长度
	int S[MAX_SIZE] = { 0 };	//已求得最短路径的终点的集合
	int predecessor[MAX_SIZE];	//存放顶点的前驱，方便输出最短路径，前驱的引入是本程序最重要的地方


	printf("请输入两个景点的代码：");
	scanf("%d %d",&adr1,&adr2);
	//对输入的两个景点进行交换，否则输出景点路径时为逆序输出
	int temp;
	temp = adr1;
	adr1 = adr2;
	adr2 = temp;

	for (int i = 0; i < MAX_SIZE; i++)	//初始化所有顶点的前驱都为起始景点
		predecessor[i] = adr1;

	for (int j = 0; j < MAX_SIZE; j++)
		D[j] = arcs[adr1][j];

	for (int i = 0; i < MAX_SIZE; i++) {
		for (int j = 0; (j < MAX_SIZE); j++) {
			if (j == adr1)	//防止寻找到的路径的起始点和终点相同
				continue;
			if (D[min] + arcs[min][j] < D[j]) {
				D[j] = D[min] + arcs[min][j];
				predecessor[j] = min;	//	前驱的建立
			}
		}
		min = search_min(D, S, i);	//	寻找当前最短路径，返回最短路径的终点

		if (min == -1) {	
			printf("非连通图，最短路径查询失败\n");
			exit(0);
		}

		S[i] = min;		//编号为min的顶点作为最短路径的终点，所以把此顶点放入S中
		if (min == adr2)	//如果现在选择的最短路径的终点恰好是adr2，则停止寻找最短路径，减少时间复杂度
			break;

	}
	//输出最短路径的信息
	int pre = adr2;		//注意，前面对adr1和adr2进行了交换
	printf("从%s到%s的路径长度为%d,现在输出路径信息\n", position[adr2].name,position[adr1].name,D[adr2]);
	for (int i = 0; pre != adr1; i++) {
		printf("%s-->",position[pre].name);
 		pre = predecessor[pre];
	}
	printf("%s", position[adr1].name);

}
int main()
{
	Scenic_sports position[MAX_SIZE] = {
		{"北门",0,"北门外原先有个集，后来政府说没有它就没有了"},
		{"校医院",1,"医术不敢恭维，但报销之后药挺便宜的，小病可以去校医院看"},
		{"北区公寓",2,"三个宿舍区域之一，离教学区最近，早上可以起的比东区南区晚一点"},
		{"北操",3,"来凑个数"},
		{"餐厅",4,"吃饭的地方，有一餐，二餐和清真"},
		{"东操",5,"凑数+1"},
		{"九球广场",6,"九个石头蛋，一个没有广场舞的广场"},
		{"五子顶",7,"海大崂山校区海拔最高的地方，有机会要爬上去看一看"},
		{"保研路",8,"暂无官方介绍"},
		{"行远楼",9,"海大行远楼，一跃解千愁，是一座行政楼"},
		{"孔子像",10,"每到期末考试的时候，孔子总是会收到很多贡品"},
		{"图书馆",11,"在里面自习比较宽敞，建议搬到北区"}
	};
	printf("********欢迎来到中国海洋大学景点查询系统********\n");
	printf("学校景点如下\n");
	for (int i = 0; i < MAX_SIZE; i++) 
		printf("代码：%d，名称：%s\n", position[i].code, position[i].name);
	
	printf("查询景点详细信息请按1，查询景点间的最短路径请按2\n");
	int func;
	scanf("%d", &func);
	if (func == 1)
		get_info(position);
	else if (func == 2)
		get_shortest_path(position);

}



引入前驱的思想不是我的原创，参考博客：https://blog.csdn.net/littlehedgehog/article/details/1758701

如果程序中有bug或者博客里有写错的地方，欢迎大家批评指正。