数据结构——基于 Dijsktra 算法的最短路径求解

悠悠 2022-12-29 01:50 109阅读 0赞

实验七 基于 Dijsktra 算法的最短路径求解  
【实验目的】

1.  掌握图的邻接矩阵表示法，掌握采用邻接矩阵表示法创建图的算法。
2.  掌握求解最短路径的 Dijsktra 算法。  
    【实验内容】  
    问题描述  
    一张地图包括 n 个城市,假设城市间有 m 条路径(有向图),每条路径的长度  
    已知。给定地图的一个起点城市和终点城市,利用 Dijsktra 算法求出起点到终  
    点之间的最短路径。  
    输入要求  
    多组数据,每组数据有 m+3 行。第一行为两个整数 n 和 m,分别代表城市个数  
    n 和路径条数 m。第二行有 n 个字符,代表每个城市的名字。第三行到第 m+2 行每  
    行有两个字符 a、b 和一个整数 d,代表从城市 a 到城市 b 有一条距离为 d 的路。  
    最后一行为两个字符,代表待求最短路径的城市起点和终点。当 n 和 m 都等于 0  
    时,输人结束。  
    输出要求  
    每组数据输出2行。第1行为一个整数,为从起点到终点之间最短路的长度。  
    第 2 行为一串字符串,代表该路径。每两个字符之间用空格隔开。  
    输入样例  
    3 3  
    A B C  
    A B 1  
    B C 1  
    C A 3  
    A C  
    6 8  
    A B C D E F  
    A F 100  
    A E 30  
    A C 10  
    B C 5  
    C D 50  
    E D 20  
    E F 60  
    D F 10  
    A F  
    0 0  
    输出样例  
    2  
    A B C  
    60  
    A E D F  
    【实验提示】  
    此实验内容即为教材算法 7.15 的扩展，原算法求出源点 v0 到图中其余所有  
    顶点的最短路径。本实验要求求出一个指定起点到一个指定终点的最短路径。  
    为了提高算法的效率,在求解时,可以加以判断,当已求得的终点为指定终点  
    时,则可以终止求解,按要求输出相应结果。

#include<stdio.h>
    #include<string.h>
    #define INF 32767
    #define MAXVEX 30
    int dist[MAXVEX];		 //建立dist数组
       int path[MAXVEX];		 //建立path数组
       int S[MAXVEX];		 //建立S数组
    
    typedef char VertexType;
    
    
    typedef struct graph
    {
        
    	int n,e;
    	VertexType vexs[MAXVEX];
    	int edges[MAXVEX][MAXVEX];
    }MGraph;
    
    void CreateMGraph(MGraph &G,int n,int e)
    {
        
    
    	int value;
    
    	char temp_i;
    	char temp_j;
    	
    
       
        G.n=n;G.e=e;
        
        
        
        for(int i=0;i<n;i++)
        {
        
        	for(int j=0;j<n;j++)
        	{
        
        		if(i==j)
        			G.edges[i][j]=0;
        		else
        			G.edges[i][j]=32767;
    		}
    		
    	}
    	
    	
    	
    
    		for(int j=0;j<G.n;j++)
    		{
        
    			getchar();
    			scanf("%c",&G.vexs[j]);
    			
    		}
    		
    			
    		
    		int temp_number_i;
    		int temp_number_j;
    		
    
    		for(int j=0;j<e;j++)
    		{
        
    			getchar();
    			scanf("%c %c %d",&temp_i,&temp_j,&value);
    			for(int i=0;i<n;i++)
    			{
        
    				if(G.vexs[i]==temp_i)
    					temp_number_i=i;
    				if(G.vexs[i]==temp_j)
    					temp_number_j=i;
    			}
    			G.edges[temp_number_i][temp_number_j]=value;
    		}
    	
    	
    
    		
    		
    	
    }
    
    void DispMGraph(MGraph &G)
    {
        
    	printf("输出顶点信息：\n");
    	for(int i=0;i<G.n;i++)
    	{
        
    		printf("%c",G.vexs[i]);
    	} 
    	printf("\n输出邻接矩阵：\n");
    	printf("\t");
        for(int i=0;i<G.n;i++)
            printf("%8c",G.vexs[i]); 
            
        for(int i=0;i<G.n;i++)
        {
        
        	printf("\n%8c",G.vexs[i]);
        	for(int j=0;j<G.n;j++)
        	{
        
        		if(G.edges[i][j]==32767) 
            //两点之间无连接时权值为默认的32767，
           // 在无向图中一般用"0"表示，在有向图中一般用"∞",
           // 这里为了方便统一输出 "∞"
                printf("%8s", "∞");
            else
                printf("%8d",G.edges[i][j]);
    		}
    		printf("\n");
    	}
    }
    
    void Dijkstra(MGraph g, int v)
    {
          
       //求从v到其他顶点的最短路径
       int mindis,i,j,u=0;
       for (i=0;i<g.n;i++)
       {
        	dist[i]=g.edges[v][i]; //距离初始化
    	S[i]=0;			 //S[]置空
    	if (g.edges[v][i]<INF) //路径初始化
    	path[i]=v;		 //v→i有边时，置i前一顶点为v
    	else			 //v→i没边时，置i前一顶点为-1
    	path[i]=-1;
       }
       S[v]=1;			//源点编号v放入S中
       for (i=0;i<g.n-1;i++)	//循环向S中添加n-1个顶点
       {
          mindis=INF;		//mindis置最小长度初值
          for (j=0;j<g.n;j++)	//选取不在S中且有最小距离顶点u
    	if (S[j]==0 && dist[j]<mindis) 
    	{
          u=j;
    	   mindis=dist[j];
    	}
          S[u]=1;			//顶点u加入S中
          for (j=0;j<g.n;j++)	//修改不在s中的顶点的距离
    	 if (S[j]==0)
    	   if (g.edges[u][j]<INF
                    && dist[u]+g.edges[u][j]<dist[j])
    	{
          dist[j]=dist[u]+g.edges[u][j];
    	      path[j]=u;
    	   }
       }
    }
    
    void Print(MGraph G,int v,int w)
    {
        
        printf("\n");
        for(int i=0;i<G.n;i++){
        
            if(i!=v && dist[i]!=INF&&i==w){
        
                printf("%c到%c的最短距离为：%d\n",G.vexs[v],G.vexs[i],dist[i]);
            }else if(dist[i]==INF&&i==w){
        
               printf("%c与%c之间无路径！\n",G.vexs[v],G.vexs[i]); 
            } 
        }
    }
    
    
    
    static void Dispath(MGraph g, int v,int w)
    {
        
        int i, j, k;
        int apath[MAXVEX], d;                         //存放一条最短路径(逆向)及其顶点个数
    
        //循环输出从顶点v到i的路径
        for(i = 0; i < g.n; i++)
        {
        
            if(S[i] == 1 && i != v&&i==w)
            {
        
               
                printf("%d\n",dist[i]);
                d = 0; apath[d] = i;                //添加路径上的终点
                k = path[i];
                if(k == -1)                         //没有路径的情况
                    printf("无路径\n");
                else                                //存在路径时输出该路径
                {
        
                    while(k != v)
                    {
        
                        d++;
                        apath[d] = k;
                        k = path[k];
                    }
                    d++; apath[d] = v;	              //添加路径上的起点
                    
                    printf("%c ",  g.vexs[apath[d]]);         //先输出起点
                    for(j = d - 1; j >= 0; j--)     //再输出其余顶点
                        printf("  %c ", g.vexs[apath[j]]);
                    printf("\n");
                }
            }
        }
    }
    
    
    int main()
    {
        
    	MGraph G;
    	int n,e;
    	
    	do{
        
    		scanf("%d%d",&n,&e);
    	
    	if(n==0&&n==0)
    		break;
    	
    	CreateMGraph(G,n,e);
    
    	char a,b;
    	getchar();
    	scanf("%c %c",&a,&b);
    	
    	int indexa,indexb;
    	
    	for(int i=0;i<G.n;i++)
    	{
        
    		if(a==G.vexs[i])
    			indexa=i;
    		if(b==G.vexs[i])
    			indexb=i; 
    	}
    	
    	
    	Dijkstra(G,indexa);
    	
    
    	
    	Dispath(G,indexa,indexb);
    	
    	
    	
    	
    	
    	
    	
    	
    		
    	}while(1);
    	return 0;
    	
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221120/da1c1ec2f37f49fd8ab5176f79f242e0.png