图的最短路径（dijkstra算法）

本文主要是介绍图的最短路径（dijkstra算法），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

洛谷有题

P3371 【模板】单源最短路径（弱化版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P4779 【模板】单源最短路径（标准版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 

先放大佬的ac代码（请看第一篇题解，写的很不错！）

P4779 【模板】单源最短路径（标准版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Floyd算法是求任意两点的最短路径

(5条消息) 《算法笔记》—— 图 "最短路径" 之 Floyd-Warshall算法、Diljkstra算法_浪子花梦-CSDN博客 

邻接矩阵方法

考试必要理解的diljkstra（模板），老师给的

/* 
* 单源最短路径，Dijkstra算法，邻接矩阵形式，复杂度为O(n^2) 
* 求出源beg到所有点的最短路径，传入图的顶点数，和邻接矩阵cost[][] 
* 返回各点的最短路径lowcost[], 路径pre[].pre[i]记录beg到i路径上的父结点，pre[beg]=-1 
* 可更改路径权类型，但是权值必须为非负 
* 
*/ 
const int MAXN=1010; 
#define typec int 
const typec INF=0x3f3f3f3f;//防止后面溢出，这个不能太大 
bool vis[MAXN]; //判断顶点所属集合标志数组
int  pre[MAXN]; //双亲数组 记录路径
void Dijkstra(typec cost[][MAXN],typec lowcost[],int n,int beg) 
{ 
	for(int i=0;i<n;i++)     //初始化，使得每一条路径最大，n为顶点数
	{ 
		lowcost[i]=INF;
        vis[i]=false;      //这个数组记录未被访问的结点，后续判断要用
        pre[i]=-1; 
	} 
	lowcost[beg]=0;    //起点到起点路径为0 
	
    
    for(int j=0;j<n;j++) //
	{ 
		int k=-1; 
		int Min=INF; 
		for(int i=0;i<n;i++) //先找出最小的未访问的最小顶点k
			if(!vis[i]&&lowcost[i]<Min) 
			{ 
				Min=lowcost[i]; //一直循环找最小
				k=i; 
			} 

		if(k==-1)  //如果把所有的lowcost遍历一遍都找到了最短路径，则退出循环结束
                break; 

		vis[k]=true; //将新找到的当前最小结点设置为“已访问”

        /*
        此时将当前最小结点置入lowcost后,更新所有从k结点出发到任意一顶点的路径(松弛)，
        这时候可以把下一个结点的最短路径求出
        */
		for(int i=0;i<n;i++) 
		    if(!vis[i] && lowcost[k]+cost[k][i]<lowcost[i]) //松弛
		    { 
			    lowcost[i]=lowcost[k]+cost[k][i]; 
			    pre[i]=k; 
		    } 
	} 

怎么打印路径以及邻接表的dijikstra算法在下面的一个博客可以找到答案

Dijkstra算法打印路径+邻接表

(5条消息) Dijkstra基于邻接表算法C++实现_优雅~天宫雁-CSDN博客 

这篇关于图的最短路径（dijkstra算法）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！