单源最短路问题--朴素Dijkstra & 堆优化Dijkstra

许久没有写博客，更新一下~

Dijkstra两种典型写法

1. 朴素Dijkstra     时间复杂度O(N^2)       适用：稠密图（点较少，分布密集）

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

const int N=;

int n, m;

int g[N][N], dist[N];

bool st[N];

int dijkstra()

{

    memset(dist, 0x3f, sizeof(dist));

    dist[]=;

    for(int i=; i<n; i++)

    {

        int t=-;

        for(int j=; j<=n; j++)

            if(!st[j] && (t==- || dist[t]>dist[j])) t=j;  //1. S中求最近的点，目前到起点的最小值

        st[t]=true;                 //2. 更新状态 t点到起点的最短路已经被确定

        for(int j=; j<=n; j++)

            dist[j]=min(dist[j], dist[t]+g[t][j]);  //3. 用t更新，经过t可能构成的最短路

    }

    if(dist[n]==0x3f3f3f3f) return -;

    else return dist[n];

}

int main()

{

    scanf("%d%d", &n, &m);

    memset(g, 0x3f, sizeof(g));

    for(int i=; i<m; i++)

    {

        int x, y, z;

        scanf("%d%d%d", &x, &y, &z);

        g[x][y]=min(g[x][y], z);

    }

    printf("%d\n", dijkstra());

    return ;

}

2. 堆优化Dijkstra　　时间复杂度：O(m*log(n)) 　　适合：稀疏图（边较多，点分布不集中）

#include <cstdio>

#include <iostream>

#include <queue>

#include <cstring>

using namespace std;

const int N=1e5+;

typedef pair<int, int> PII;

int h[N], e[N], ne[N], w[N], idx;

bool st[N];

int n, m, dist[N];

void add(int a, int b, int c)

{

    e[idx]=b, ne[idx]=h[a], w[idx]=c, h[a]=idx++;    //建图

}

int dijkstra()

{

    memset(dist, 0x3f, sizeof(dist));

    dist[]=;

    priority_queue<PII, vector<PII>, greater<PII>> heap;

    heap.push({, });

    while(heap.size())

    {

        auto u=heap.top();      //取已确定到起点最小距离的点， O(1)

        heap.pop();

        int ver=u.second, dis=u.first;

        if(st[ver]) continue;

        st[ver]=true;

        for(int i=h[ver]; i!=-; i=ne[i])

        {

            int j=e[i];

            if(!st[j] && dist[j]>dis+w[i])    //这里的dis可以写成dist[ver]

            {                                   //用pair存储距离、节点编号，为了以 距离 建堆

                dist[j]=dist[ver]+w[i];     //注意这里的w[i] , 边的权值存储在节点对应位置

                heap.push({dist[j], j});  //入堆，O(log(n))

            }                                //每一条边都会被遍历到,总时间复杂度O(m*log(n))

        }

    }

    if(dist[n]==0x3f3f3f3f) return -;

    else return dist[n];

}

int main()

{

    scanf("%d%d", &n, &m);

    memset(h, -, sizeof(h));

    while(m--)

    {

        int a, b, c;

        scanf("%d%d%d", &a, &b, &c);

        add(a, b, c);

    }

    printf("%d\n", dijkstra());

    return ;

}