最短路径（dijkstra算法）

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

dijkstra算法

///不适用于边的权值为负值

void Dijkstra(Graph G,int v){
	int s[G.vexnum];  //标记数组
	int path[G.vexnum];  //路径数组
	int dist[G.vexnum];  //最短路径数组
	
	for(int i=0;i<G.vexnum;i++){
		dist[i]=G.edge[v][i];
		s[i]=0;
		if(G.edge[v][i]<max) path[i]=v;
		else path[i]=-1;
	}
	s[v]=1;  //v已经加入
	path[v]=-1;   //v的前一个节点 初始化为-1
} 

for(int i=0;i<G.vexnum;i++){
	int min=max;
	int u;
	
	for(int j=0;j<G.vexnum;j++){
		if(s[j]==0 && dist[j]<min){
			min=dist[j];   //最短路径
			u=j;   //节点
		}
		s[u]=1;   //将u节点标记为已经加入
	}
	for(int j=0;j<G.vexnum;j++){
		if(s[j]==0 && dist[u]+G.Edge[u][j]<dist[j]){
			dist[j]=dist[u]+G.Edges[u][i];  //更新数组dist[]
			path[j]=u;           //j的前一个节点为u
		}
	}
}

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