dijkstra算法c++详细解释

Dijkstra算法是一种单源最短路径算法，用于求解从一个顶点出发到其他所有顶点的最短路径。它的基本思想是：每次找到当前最短的距离未确定的顶点，确定它的最短路径，并用它更新其他顶点的距离。具体地，算法包括以下几个步骤：

1.初始化：将起始点s到自身的距离置为0，将其余顶点到s的距离置为无穷大。

2.找到当前未确定的距离最小的顶点u，并将其标记为已确定。

3.根据顶点u的更新其他顶点的距离，具体地，遍历与u相邻的所有顶点，如果u到该顶点的距离加上u到起始点s的距离小于该顶点到起始点s的距离，则更新该顶点的距离。

4.重复执行2-3步，直到所有顶点的最短路径被确定。

以下是一个基于邻接表的Dijkstra算法C++代码实现：

#include<bits/stdc++.h>
using namespace std;

const int N=100010,M=200010;

int h[N],e[M],w[M],ne[M],idx;
int dist[N];
bool st[N];
int n,m;

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int dijkstra()
{
    // 初始化距离数组和标记数组
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    // 小根堆存储当前未确定最短路径的顶点
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
    q.push({0,1});

    while(q.size())
    {
        auto t=q.top();
        q.pop();

        int ver=t.second,distance=t.first;

        // 如果该顶点已经确定最短路径，则跳过
        if(st[ver]) continue;
        st[ver]=true;

        // 遍历与该顶点相邻的所有顶点
        for(int i=h[ver];~i;i=ne[i])
        {
            int j=e[i];
            // 如果通过该顶点到达另一个顶点的距离加上该顶点到起点的距离小于该顶点到起点的距离，则更新该顶点的距离
            if(dist[j]>distance+w[i])
            {
                dist[j]=distance+w[i];
                q.push({dist[j],j});
            }
        }
    }

    // 如果无法到达终点，则返回-1
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    // 初始化邻接表
    memset(h,-1,sizeof h);
    cin>>n>>m;

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }

    // 输出起点到终点的最短距离
    cout<<dijkstra()<<endl;

    return 0;
}

在以上代码中，我们使用了一个小根堆来存储当前未确定最短路径的顶点，每次从中取出距离最小的顶点进行更新。同时，我们使用了一个标记数组来判断该顶点是否已经确定最短路径，避免重复更新。最后，如果无法到达终点，则返回-1。