怎么用狄杰斯特拉算法（Dijkstra）求解下图最短路径

核心思想：找一个未被选过的，距离最短的点。每次用具有这个属性的点—-对它直接连接到的点进行更新。

例题：怎么用狄杰斯特拉算法（Dijkstra）求解下图最短路径

首先我们规定从 $v_{0}$ 开始

此时可以绘制以下表格：怎么用狄杰斯特拉算法（Dijkstra）求解下图最短路径

假设我们将源点选择在 $v_{0}$ 这个点。一开始所有点到达源点 $v_{0}$ 的距离我们假设为∞。

然后我们布置两个集合。A用来存放已经求出最短路径的点，B用来存放还未计算出最短路径的点。此时A集合为：{0}，B集合为：{1，2，3，4，5，6}。

进行第一次更新，：

我们来看， $v_{0}$ 直接相连接的有四个点， $v_{4} v_{2} v_{1} v_{6}$ ，那么我们更新这四个点的距离。其余两点保持距离为∞。

怎么用狄杰斯特拉算法（Dijkstra）求解下图最短路径

表格更新为：

怎么用狄杰斯特拉算法（Dijkstra）求解下图最短路径

接下来选择下一个距离最短的点 —- $v_{2}$ 。

这个时候， $v_{2}$ 就定死了，再也没有能比从 $v_{0}$ 到 $v_{2}$ 更短的距离了。所以，此时集合更新为：A集合为：{2}，B集合为：{1，3，4，5，6}。

$v_{2}$ 能更新的点为—— $v_{3}$

怎么用狄杰斯特拉算法（Dijkstra）求解下图最短路径

表格更新为：

怎么用狄杰斯特拉算法（Dijkstra）求解下图最短路径

接下来选择下一个距离最短的点 —- $v_{1}$ 。（距离相同选靠前的点）

此时集合更新为：A集合为：{2，1}，B集合为：{3，4，5，6}。

$v_{1}$ 可以更新 $v_{5} v_{6}$

怎么用狄杰斯特拉算法（Dijkstra）求解下图最短路径

$v_{5}$ 从∞变成22， $v_{6}$ 原来是32，现在是20，变小了，更新掉。

此时表格为：怎么用狄杰斯特拉算法（Dijkstra）求解下图最短路径

接下来选择下一个距离最短的点 —- $v_{3}$ 。

此时集合更新为：A集合为：{2，1，3}，B集合为：{4，5，6}。

$v_{3}$ 可以更新 $v_{4}$

怎么用狄杰斯特拉算法（Dijkstra）求解下图最短路径

$v_{4}$ 被更新为19，此时表格为：

怎么用狄杰斯特拉算法（Dijkstra）求解下图最短路径

接下来选择下一个距离最短的点 —- $v_{4}$ 。

此时集合更新为：A集合为：{2，1，3，4}，B集合为：{5，6}。

$v_{4}$ 可以更新 $v_{5}$

怎么用狄杰斯特拉算法（Dijkstra）求解下图最短路径

$v_{5}$ 被更新为21，此时表格为：怎么用狄杰斯特拉算法（Dijkstra）求解下图最短路径

此时，B集合中：{5，6} 最短距离点为 $v_{6}$ 。

$v_{6}$ 更新不了任何点，即直接放入集合A即可，到此更新结束。

A集合为：{2，1，3，4，6，5}，B集合为：{}。

核心代码：

#include
using namespace std;
const int N=501;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra(){
	dist[1]=0;
	//st[1]=1;
    //不能写st[1]=1,因为把1当成第一个最近的节点来更新
    //入过直接把st[1]=1，在第一次循环的时候就没有“最近的点”
	for(int i=0;i<n-1;i++){
		//n-1次，每次将1个节点的st改为1 
		//每次刚开始确认一个节点的时候，将这个节点先设成-1 
		int t=-1;
		for(int j=1;j<=n;j++){
			//找没有被确定且距离最近的点 
			if(!st[j]&&(t==-1||dist[j]<dist[t])){
				t=j;
			}
		}
		//找到节点t，将t的st更新为1 
		st[t]=1;
		if(t==n) break;//提前找到n，break
		//再用t去试图更新其它节点的距离
		//这个写法很棒，省去很多判断 
		for(int j=1;j>n>>m;
	memset(g,0x3f,sizeof g);
	memset(dist,0x3f,sizeof dist);
	for(int i=1;i>a>>b>>c;
		
		g[a][b]=min(g[a][b],c);
		// 去除重环 
	}
	cout<<dijkstra();	
}

最后写一点概念：

Dijkstra算法是路径规划算法中非常经典的一种算法，在很多地方都会用到，特别是在机器人的路径规划中，基本学习机器人运动相关的都会接触到该算法。Dijkstra算法本身的原理是基于贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

1.指定一个节点，例如我们要计算 ‘A’ 到其他节点的最短路径

算法思路：

2.引入两个集合（S、U），S集合包含已求出的最短路径的点（以及相应的最短长度），U集合包含未求出最短路径的点（以及A到该点的路径，注意如上图所示，A->C由于没有直接相连初始时为∞）

3.初始化两个集合，S集合初始时只有当前要计算的节点，A->A = 0，U集合初始时为 A->B = 4, A->C = ∞, A->D = 2, A->E = ∞，敲黑板！！！接下来要进行核心两步骤了

4.从U集合中找出路径最短的点，加入S集合，例如 A->D = 2

5.更新U集合路径，if ( ‘D 到 B,C,E 的距离’ + ‘AD 距离’ < ‘A 到 B,C,E 的距离’ ) 则更新U

6.循环执行 4、5 两步骤，直至遍历结束，得到A 到其他节点的最短路径

尾：这个算法我的老师上课讲了两遍！讲的很清楚好感动！and 感谢负责编辑@lyt_cg 的耐心讲解耶！讲的很棒才有了这篇博客！嘿嘿！好耶~

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/6525c17345.html