什么是Dijkstra算法
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又 叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最 短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍 历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
Dijkstra是求单源最短路问题的经典算法，单源最短路一般来说是求一个点到其他点的 最短距离，最常见的一种题型是求1号点到n号点的最短距离。
而单源最短路又分为两种，一种是边权全为正(正权值)，另一种是存在负权边。Dijkstra 用来解决边权全为正的单源最短路问题，Dijkstra算法又分为朴素Dijkstra算法和堆优化 的Dijkstra算法。朴素版的Dijkstra算法的时间复杂度是O(n²),适合于稠密图，堆优化版 的Dijkstra算 法的时间复杂度是O(mlogn)，适合于稀疏图。
解决存在负权边的单源最短路的算法又分为两种，一个是Bellman-Ford，一个是SPFA， SPFA是Bellman-Ford算法的优化。
朴素版Dijkstra算法思路
- 先初始化距离，1号点到起点的距离是0，其他点到起点的距离是无穷大
- 第二步是一个迭代的过程，循环n次，找到没有确定最短距离且距离起点最近的点，用这个点更新其他点的距离，这个点同时也确定了最短距离。循环n次就可以确定n个点到起点的距离了
举个栗子
以这个为例，一共三个点，绿色的数字表示点与点之间的距离，1号点到2号点的 距离是2，2号点到3号点的距离是1，1号点到3号点的距离是4，红色数字 表 示每个点到起点的距离。
按照朴素版Dijkstra算法的步骤，首先要初始化距离，1号点到起点的距离是0， 其他点到起点的距离是正无穷
然后我们就要循环3次，确定每个点到起点的距离
第一次循环
第一次循环明显是1号点距离起点最近，所以我们用这个点更新一下和它相连的点 距离起点的距离，也就是2,3号点，更新之后2号点距离起点的距离是2,3号点距 离起点的距离是4
第二次循环
第二次循环发现是2号点距离起点最近，用2号点更新一下和它相连的点距离起点的距离，也就是3号点。3号点距离起点的距离在第一次循环时更新为4，这次我们用2号点更新时可以发现，3号点距离起点的距离可以更新为3，也就1->2->3 的路线的距离小于1->4的路线，所以把3号点距离起点的距离改为3
第三次循环
第三次循环只剩一个点3了，这个点可以确定最短距离是3，至此循环结束，所有的点距离起点的最短距离也就确定了
朴素版Dijkstra存储
上面说了朴素版Dijkstra算法适用于稠密图，稠密图用邻接矩阵来存
案例-Dijkstra求最短路1
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 nn 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n≤500,
1≤m≤1e5,
图中涉及边长均不超过10000。输入样例：
3 3 1 2 2 2 3 1 1 3 4输出样例：
3
代码实现
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=515;
int dist[N];//每个点距离起点的距离
int g[N][N];//邻接矩阵
int n,m;
bool st[N];//存储已经确定最短路径的点
int dijkstra()
{
//初始化每个点到起点的距离
memset(dist,0x3f,sizeof dist);
//1号点到起点的距离为0
dist[1]=0;
//循环n次确定n个点到起点的最短距离
for(int i=0;i<n;i++)
{
//每次循环用t来存没有确定最短距离且距离起点最近的点
int t=-1;
for(int j=1;j<=n;j++)
{
if(!st[j]&&(t==-1||dist[j]<dist[t]))
t=j;
}
//确定了距离起点最近的点，将它标记
st[t]=true;
//用这个点更新和它相连的点距离起点的距离
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
cin>>n>>m;
//初始化邻接矩阵
memset(g,0x3f,sizeof g);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
//如果有重边的话，取最小的那条边,自环遍历不到不再考虑
g[a][b]=min(g[a][b],c);
}
int t=dijkstra();
cout<<t;
return 0;
}注意：对于自环是遍历不到的，而重边只取其中最短的一条
堆优化版Dijkstra算法
当图为稀疏图时，也就是点数和边数在一个数量级上时我们就要用上堆优化版的Dijkstra 算法了，什么是堆优化Dijkstra算法呢？朴素版的Dijkstra算法慢就慢在寻找没有确定 最短距离且距离起点最近的点这里，这里我们用堆来找可以提高速度，这个也就是堆优化Dijkstra算法了，堆优化Dijkstra也就是对朴素版的查找部分用堆来优化了一下。
堆有两种实现方法，一个是手写堆，一个是优先队列，这里我们用优先队列来做。
步骤和朴素版类似，这里就不赘述了。
堆优化Dijkstra存储
堆优化Dijkstra算法适用于稀疏图，稀疏图用邻接表来存。
案例-Dijkstra求最短路2
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n,m≤1.5*1e5,
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 1e9。输入样例：
3 3 1 2 2 2 3 1 1 3 4输出样例：
3
代码实现
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N=1e6+10;
typedef pair<int,int>pll;//存储距离和编号，用于小根堆
int h[N],e[N],ne[N],idx,w[N];//邻接表,w数组表示权重，idx是两个点之间的桥梁
int n,m;
int dist[N];//每个点距离起点的距离
bool st[N];
//邻接表模板
void add(int a,int b,int c)
{
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
int dijkstra()
{
//初始化距离，1号点距离为0
memset(dist,0x3f,sizeof dist);
dist[1]=0;
//小根堆，自动升序排列
priority_queue<pll,vector<pll>,greater<pll>> heap;
heap.push({0,1});
while(heap.size())
{
//取出堆顶元素
auto t=heap.top();
//弹出堆顶元素
heap.pop();
//获得堆顶元素的距离和编号
int ver=t.second,distance=t.first;
if(st[ver]) continue;
st[ver]=true;
//通过这个点更新和它相连的点距离起点的距离
for(int i=h[ver];i!=-1;i=ne[i])
{
int j=e[i];//获得编号
//如果这个点距离起点的距离可以更新的话
if(dist[j]>distance+w[i])//遍历所有重边，使用距离最小的重边来更新
{
dist[j]=distance+w[i];
heap.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
cin>>n>>m;
//初始化h数组
memset(h,-1,sizeof h);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
//这里不考虑重边
add(a,b,c);
}
int t=dijkstra();
cout<<t;
return 0;
}注意：初始化点与点之间的距离时不用考虑重边的问题，我们这里用邻接表存储，会遍历所有的重边，会选择距离最小的重边更新到起点的距离文章来源：https://www.toymoban.com/news/detail-841883.html
这类题不用考虑是无向图还是有向图，因为无向图是特殊的有向图，无向图可以看成有一个去的路也有一个回来的路
如有错漏之处，敬请指正！ 文章来源地址https://www.toymoban.com/news/detail-841883.html
到了这里，关于Dijkstra算法详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
