【数据结构】最短路径_Dijkstra的创建（C语言）

灰太狼 2023-02-25 02:03 10阅读 0赞

#include "stdio.h"    
    #include "stdlib.h"   
    #include "io.h"  
    #include "math.h"  
    #include "time.h"
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    #define MAXEDGE 20
    #define MAXVEX 20
    #define INFINITY 65535
    
    typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码，如OK等 */ 
    
    
    typedef struct
    {
        
    	int vexs[MAXVEX];
    	int arc[MAXVEX][MAXVEX];
    	int numVertexes, numEdges;
    }MGraph;
    
    typedef int Patharc[MAXVEX];    /* 用于存储最短路径下标的数组 */
    typedef int ShortPathTable[MAXVEX];/* 用于存储到各点最短路径的权值和 */
    
    /* 构件图 */
    void CreateMGraph(MGraph *G)
    {
        
    	int i, j;
    
    	/* printf("请输入边数和顶点数:"); */
    	G->numEdges=16;
    	G->numVertexes=9;
    
    	for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    	{
        
    		G->vexs[i]=i;
    	}
    
    	for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    	{
        
    		for ( j = 0; j < G->numVertexes; j++)
    		{
        
    			if (i==j)
    				G->arc[i][j]=0;
    			else
    				G->arc[i][j] = G->arc[j][i] = INFINITY;
    		}
    	}
    
    	G->arc[0][1]=1;
    	G->arc[0][2]=5; 
    	G->arc[1][2]=3; 
    	G->arc[1][3]=7; 
    	G->arc[1][4]=5; 
    
    	G->arc[2][4]=1; 
    	G->arc[2][5]=7; 
    	G->arc[3][4]=2; 
    	G->arc[3][6]=3; 
    	G->arc[4][5]=3;
    
    	G->arc[4][6]=6;
    	G->arc[4][7]=9; 
    	G->arc[5][7]=5; 
    	G->arc[6][7]=2; 
    	G->arc[6][8]=7;
    
    	G->arc[7][8]=4;
    
    
    	for(i = 0; i < G->numVertexes; i++)
    	{
        
    		for(j = i; j < G->numVertexes; j++)
    		{
        
    			G->arc[j][i] =G->arc[i][j];
    		}
    	}
    
    }
    
    /*  Dijkstra算法，求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v] */    
    /*  P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和 */  
    void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
    {
            
    	int v,w,k,min;    
    	int final[MAXVEX];/* final[w]=1表示求得顶点v0至vw的最短路径 */
    	for(v=0; v<G.numVertexes; v++)    /* 初始化数据 */
    	{
                
    		final[v] = 0;			/* 全部顶点初始化为未知最短路径状态 */
    		(*D)[v] = G.arc[v0][v];/* 将与v0点有连线的顶点加上权值 */
    		(*P)[v] = -1;				/* 初始化路径数组P为-1  */       
    	}
    
    	(*D)[v0] = 0;  /* v0至v0路径为0 */  
    	final[v0] = 1;    /* v0至v0不需要求路径 */        
    	/* 开始主循环，每次求得v0到某个v顶点的最短路径 */   
    	for(v=1; v<G.numVertexes; v++)   
    	{
        
    		min=INFINITY;    /* 当前所知离v0顶点的最近距离 */        
    		for(w=0; w<G.numVertexes; w++) /* 寻找离v0最近的顶点 */    
    		{
                    
    			if(!final[w] && (*D)[w]<min)             
    			{
                           
    				k=w;                    
    				min = (*D)[w];    /* w顶点离v0顶点更近 */            
    			}        
    		}        
    		final[k] = 1;    /* 将目前找到的最近的顶点置为1 */
    		for(w=0; w<G.numVertexes; w++) /* 修正当前最短路径及距离 */
    		{
        
    			/* 如果经过v顶点的路径比现在这条路径的长度短的话 */
    			if(!final[w] && (min+G.arc[k][w]<(*D)[w]))   
    			{
         /*  说明找到了更短的路径，修改D[w]和P[w] */
    				(*D)[w] = min + G.arc[k][w];  /* 修改当前路径长度 */               
    				(*P)[w]=k;        
    			}       
    		}   
    	}
    }
    
    int main(void)
    {
           
    	int i,j,v0;
    	MGraph G;    
    	Patharc P;    
    	ShortPathTable D; /* 求某点到其余各点的最短路径 */   
    	v0=0;
    	
    	CreateMGraph(&G);
    	
    	ShortestPath_Dijkstra(G, v0, &P, &D);  
    
    	printf("最短路径倒序如下:\n");    
    	for(i=1;i<G.numVertexes;++i)   
    	{
               
    		printf("v%d - v%d : ",v0,i);
    		j=i;
    		while(P[j]!=-1)
    		{
        
    			printf("%d ",P[j]);
    			j=P[j];
    		}
    		printf("\n");
    	}    
    	printf("\n源点到各顶点的最短路径长度为:\n");  
    	for(i=1;i<G.numVertexes;++i)        
    		printf("v%d - v%d : %d \n",G.vexs[0],G.vexs[i],D[i]);     
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，10人围观）

还没有评论，来说两句吧...

相关阅读

相关基于 Dijkstra 算法最优路径规划 C 语言最短路径算法

随着科技的不断发展，越来越多的人开始关注最优路径规划问题。这个问题在我们日常生活中也有很多应用，例如地图导航、物流配送、行车路线规划等等。在实际应用中，如何快速高效地求解最短路

朴灿烈づ我的快乐病毒、/ 2023年10月13日 19:15/ 0 赞/ 82 阅读

相关【数据结构】最短路径_Dijkstra的创建（C语言）

include "stdio.h" include "stdlib.h" include "io.h" include "ma

灰太狼/ 2023年02月25日 02:03/ 0 赞/ 11 阅读

相关最短路径Dijkstra算法

最短路径Dijkstra算法本文取自《数据结构与算法》(C语言版)(第三版)，出版社是清华大学出版社。本博文作为学习资料整理。附书的截图： ![Center]

素颜马尾好姑娘i/ 2022年08月21日 03:27/ 0 赞/ 305 阅读

相关图结构练习——最短路径（Dijkstra算法）

字节跳动校招内推码: C4BDSMC 投递链接: https://job.toutiao.com/s/J691fRK 内推交流QQ群：104917572

迷南。/ 2022年07月10日 15:58/ 0 赞/ 251 阅读

相关数据结构：单源最短路径--Dijkstra算法

Dijkstra算法单源最短路径给定一带权图，图中每条边的权值是非负的，代表着两顶点之间的距离。指定图中的一顶点为源点，找出源点到其它顶点的最短路径和其长度的问

墨蓝/ 2022年06月12日 04:24/ 0 赞/ 300 阅读

相关数据结构-图（三）-最短路径之Dijkstra

Dijkstra算法用于解决单源最短路径问题，即，从一个节点出发，计算该结点到图中其他节点的最短距离。算法思想： Dijsktra提出了一个按路径长度递增的顺序逐步产生最

朱雀/ 2022年06月04日 06:50/ 0 赞/ 226 阅读

相关数据结构(十五)dijkstra单源最短路径

1 算法原理假设图中有顶点V=\{A，B，C，D，E，F\}，我们要求取A到其他顶点的最短距离。假设我们要求取定点A到其它顶点的最短路径，先把顶点A到源的距离设置为0，

喜欢ヅ旅行/ 2022年05月31日 13:38/ 0 赞/ 230 阅读

相关数据结构：最短路径算法之Dijkstra算法

Dijkstra算法 Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩

心已赠人/ 2022年05月31日 12:56/ 0 赞/ 313 阅读

相关 C语言基于Dijkstra算法的最短路径问题求解

主要思路： 1.用一个二维数组存放带权有向图的邻接矩阵； 2.基于Dijkstra算法分别申请三个数组，distance\[\], path\[\], used\[\]

淡淡的烟草味﹌/ 2022年03月10日 05:22/ 0 赞/ 253 阅读

相关 Dijkstra 最短路径

思路：两个集合： 1.visted 存储已经访问过的结点 2.unVisted 存储未遍历过的结点两个数组： 1.dist\[\] 存储1到每个结点的最

Myth丶恋晨/ 2021年09月27日 10:08/ 0 赞/ 457 阅读