Dijkstra算法详解

什么是Dijkstra算法

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又 叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最 短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍 历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

Dijkstra是求单源最短路问题的经典算法，单源最短路一般来说是求一个点到其他点的 最短距离，最常见的一种题型是求1号点到n号点的最短距离。

而单源最短路又分为两种，一种是边权全为正(正权值)，另一种是存在负权边。Dijkstra 用来解决边权全为正的单源最短路问题，Dijkstra算法又分为朴素Dijkstra算法和堆优化 的Dijkstra算法。朴素版的Dijkstra算法的时间复杂度是O(n²),适合于稠密图，堆优化版 的Dijkstra算 法的时间复杂度是O(mlogn)，适合于稀疏图。

解决存在负权边的单源最短路的算法又分为两种，一个是Bellman-Ford，一个是SPFA， SPFA是Bellman-Ford算法的优化。

朴素版Dijkstra算法思路

1. 先初始化距离，1号点到起点的距离是0，其他点到起点的距离是无穷大
2. 第二步是一个迭代的过程，循环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 
#include 
#include 
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;im;
    //初始化邻接矩阵
    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>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