最短路----Dijkstra算法详解

简介

迪杰斯特拉（Dijkstra）算法是一种用于在加权图中找到单个源点到所有其他顶点的最短路径的算法。它是由荷兰计算机科学家艾兹格·迪科斯彻（Edsger Dijkstra）在1956年提出的。Dijkstra算法适用于处理带有非负权重的图。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。适用的是单源路径最短路问题，对于多源则采用弗洛伊德（Floyd）算法

Dijkstra算法原理

1. 初始化：

   • 创建一个距离数组dist，用来存储从起始节点到每个节点的最短距离，初始时将起始节点的距离设为0，其余节点设为无穷大。
   • 创建一个优先队列（通常使用最小堆）来存储待处理的节点，初始时将起始节点加入队列。

2. 处理节点：

   • 从优先队列中取出距离最小的节点，标记为已处理。
   • 对于该节点的每个邻接节点，计算从起始节点到该邻接节点的距离。如果这个距离小于当前记录的距离，则更新距离并将该邻接节点加入优先队列。

3. 重复：

   • 重复步骤2，直到优先队列为空，或者所有节点都被处理。

如果还看不明白,请看下图

举个栗子

示例图

图的邻接表表示

• 节点0到节点1的边权重为1
• 节点0到节点2的边权重为4
• 节点1到节点2的边权重为2
• 节点1到节点3的边权重为5
• 节点2到节点4的边权重为1
• 节点4到节点3的边权重为1

Dijkstra算法执行过程

假设我们从节点0开始，以下是dist和visited数组在每一步的变化：

1. 初始化：

   • dist = [0, ∞, ∞, ∞, ∞] （从起始节点0到其他节点的距离）
   • visited = [false, false, false, false, false] （所有节点未被访问）

2. 处理节点0：

   • 当前节点：0
   • 更新邻接节点1和2：
     • dist[1] = 1（0到1的距离）
     • dist[2] = 4（0到2的距离）
   • 更新后的数组：
     • dist = [0, 1, 4, ∞, ∞]
     • visited = [true, false, false, false, false]

3. 处理节点1（下一个最小距离的节点）：

   • 当前节点：1
   • 更新邻接节点2和3：
     • dist[2] = min(4, 1 + 2) = 3（更新0到2的距离）
     • dist[3] = 1 + 5 = 6（更新0到3的距离）
   • 更新后的数组：
     • dist = [0, 1, 3, 6, ∞]
     • visited = [true, true, false, false, false]

4. 处理节点2：

   • 当前节点：2
   • 更新邻接节点4：
     • dist[4] = min(∞, 3 + 1) = 4（更新0到4的距离）
   • 更新后的数组：
     • dist = [0, 1, 3, 6, 4]
     • visited = [true, true, true, false, false]

5. 处理节点4：

   • 当前节点：4
   • 更新邻接节点3：
     • dist[3] = min(6, 4 + 1) = 5（更新0到3的距离）
   • 更新后的数组：
     • dist = [0, 1, 3, 5, 4]
     • visited = [true, true, true, false, true]

6. 处理节点3：

   • 当前节点：3
   • 由于3没有未访问的邻接节点，算法结束。
   • 最终的dist数组为：
     • dist = [0, 1, 3, 5, 4]（从节点0到各个节点的最短距离）
   • visited数组为：
     • visited = [true, true, true, true, true]（所有节点均已访问）

最终结果

• 从节点0到节点1的最短距离是1
• 从节点0到节点2的最短距离是3
• 从节点0到节点3的最短距离是5
• 从节点0到节点4的最短距离是4

这个过程展示了Dijkstra算法如何逐步更新每个节点的最短路径，并标记已访问的节点。

代码实现

#include<iostream>
using namespace std;
int n,e,s;//n个顶点，e条边，s是起点
int dis[101];//dis[i]起点到i的最短距离
int vis[101];//标记是否找到
int edge[101][101];//记录路径i->j有路径
int main()
{
	cin>>n>>e;
	for(int i=1;i<=n;i++)
	{
		dis[i]=100000;
	}
	for(int i=1;i<=e;i++)
	{//邻接矩阵存储
		int a,b,c;
		cin>>a>>b>>c;
		edge[a][b]=c;
	}
	cin>>s;
	dis[s]=0;//起点到起点不需要代价
	for(int i=1;i<=n;i++)
	{
		int minn=inf,minx;
		for(int j=1;j<=n;j++)
		{
			if(dis[j]<minn&&vis[j]==0)
			{//寻找此点到其他点的最小距离
				minn=dis[j];
				minx=j;
			}
		}
		vis[minx]=1;//标记到达的最小点
		for(int j=1;j<=n;j++)
		{
			if(edge[minx][j]>0)//有边的话 
			{
				if(minn+edge[minx][j]<dis[j])
				{
					dis[j]=minn+edge[minx][j];//更新以最小距离点最为中转点的最小距离
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{//打印最短距离
		cout<<dis[i]<<" ";
	}
	return 0;
}