dijkstra 基于贪心

⬅ 返回

1、朴素dijkstra算法适合稠密图

思路

解决图中可能存在重边和自环，所有边权均为正值的单源最短路径

📌

集合S为已经确定最短路径的点集。

1. 初始化距离 一号结点的距离为零，其他结点的距离设为无穷大（看具体的题）。
2. 循环n次，每一次将集合S之外距离最短X的点加入到S中去（这里的距离最短指的是距离1号点最近。 点X的路径一定最短，基于贪心，严格证明待看）。然后用点X更新X邻接点的距离。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
const int N = 501;
const int MAX_INT = 0x3f3f3f3f;
int g[N][N];
int dist[N];
bool st[N];
int n,m;
 
int main()
{
    cin>>n>>m;
    memset(dist,0x3f,sizeof(dist));
    memset(g,0x3f,sizeof (g));
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(g[a][b]>c)g[a][b]=c;
    }
 
    //开始Dijkstra
    dist[1]=0;//这里不要忘了 第一个点的距离为0
    for(int i=0;i<n;i++)//n个点进行n次遍历
    {
        int x=-1;
        for(int j=1;j<=n;j++)//从一号点开始 寻找没选择过的并且距离1号点距离最小的点
        {
            if(st[j]==false && (x==-1 || dist[j]<dist[x]))//这里是st[j]因为是找未被选择过的值
                x=j;
        }
 
        st[x]=true;
 
        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],dist[x]+g[x][j]);//x所指向的是目前距离1号点最短的点
    }
    if(dist[n]==MAX_INT)cout<<-1<<endl;
    else cout<<dist[n]<<endl;
}

2、堆优化版dijkstra适合稀疏图

思路

📌

堆优化版的dijkstra是对朴素版dijkstra进行了优化，在朴素版dijkstra中时间复杂度最高的寻找距离 最短的点O(n

1. 一号点的距离初始化为零，其他点初始化成无穷大。
2. 将一号点放入堆中。
3. 不断循环，直到堆空。每一次循环中执行的操作为： 弹出堆顶（与朴素版diijkstra找到S外距离最短的点相同，并标记该点的最短路径已经确定）。 用该点更新临界点的距离，若更新成功就加入到堆中。

代码

#include<iostream>
#include<cstring>
#include<queue>
 
using namespace std;
 
typedef pair<int, int> PII;
 
const int N = 100010; // 把N改为150010就能ac
 
// 稀疏图用邻接表来存
int h[N], e[N], ne[N], idx;
int w[N]; // 用来存权重
int dist[N];
bool st[N]; // 如果为true说明这个点的最短路径已经确定
 
int n, m;
 
void add(int x, int y, int c)
{
    // 有重边也不要紧，假设1->2有权重为2和3的边，再遍历到点1的时候2号点的距离会更新两次放入堆中
    // 这样堆中会有很多冗余的点，但是在弹出的时候还是会弹出最小值2+x（x为之前确定的最短路径），
    // 并标记st为true，所以下一次弹出3+x会continue不会向下执行。
    w[idx] = c;
    e[idx] = y;
    ne[idx] = h[x]; 
    h[x] = idx++;
}
 
int dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义一个小根堆
    // 这里heap中为什么要存pair呢，首先小根堆是根据距离来排的，所以有一个变量要是距离，
    // 其次在从堆中拿出来的时候要知道知道这个点是哪个点，不然怎么更新邻接点呢？所以第二个变量要存点。
    heap.push({ 0, 1 }); // 这个顺序不能倒，pair排序时是先根据first，再根据second，
                         // 这里显然要根据距离排序
    while(heap.size())
    {
        PII k = heap.top(); // 取不在集合S中距离最短的点
        heap.pop();
        int ver = k.second, distance = k.first;
 
        if(st[ver]) continue;
        st[ver] = true;
 
        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i]; // i只是个下标，e中在存的是i这个下标对应的点。
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({ dist[j], j });
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}
 
int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
 
    while (m--)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c);
    }
 
    cout << dijkstra() << endl;
 
    return 0;
}
 
作者：optimjie
链接：https://www.acwing.com/solution/content/6554/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。