最短路之dijkstra及其堆优化

解决问题

dijkstra算法用来解决单源最短路径问题
通常来说就是求解一个图中两节点的最短路径（只适用于正权边）

算法思想

该算法的朴素想法是松弛的思想
即若
dis ( 1->3 ) = 7
dis ( 1->2 ) = 1
dis ( 2->3 ) = 1
则节点2的存在就可以对1，3松弛
在松弛完一个节点之后要选择尚未进行松弛的节点松弛，且要选择距起点距离最近的点【1】

代码实现

///朴素dijkstra O(n^2+m)
int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
///代码是从y总那偷的QAQ

///堆优化的dijkstra O(mlogn)
typedef pair<int, int> PII;///改用结构体也可

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号

    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];
}

///代码是从y总那偷的QAQ

///自己写的比较顺手的dij
#include<bits/stdc++.h>
using namespace std;

struct edge
{
    int to;
    int l;
};

struct node
{
    int idx;
    int l;
    bool friend operator < (const node a, const node b)
    {
        return a.l>b.l;
    }
} d[100005];
const int inf=0x3f3f3f3f;
vector<edge> ve[100005];
priority_queue<node> qu;
bool vis[100005];

void build(int u,int v,int l)
{
    edge t;
    t.to=v,t.l=l;
    ve[u].push_back(t);
}

int main()
{
    int n,m,s;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1; i<=m; i++)
    {
        int u,v,l;
        scanf("%d%d%d",&u,&v,&l);
        build(u,v,l);
    }
    for(int i=1; i<=n; i++)
        d[i].l=inf,d[i].idx=i;
    d[s].l=0;
    qu.push(d[s]);
    while(!qu.empty())
    {
        node temp=qu.top();
        qu.pop();
        if(vis[temp.idx]) continue;
        vis[temp.idx]=1;
        int big=ve[temp.idx].size();
        for(int i=0; i<big; i++)
        {
            if(d[temp.idx].l+ve[temp.idx][i].l<d[ve[temp.idx][i].to].l)
            {
                d[ve[temp.idx][i].to].l =d[temp.idx].l+ve[temp.idx][i].l;
                    qu.push(d[ve[temp.idx][i].to]);
            }
        }
    }

    for(int i=1; i<=n; i++)
        printf("%d ",d[i].l);
    return 0;
}

【1】 因为该节点一定无法距起点更近