Dijkstra算法（朴素，堆优化）+例题

Dijkstra算法（朴素，堆优化）+例题

Dijkstra算法基于贪心，分为朴素版和堆优化版，稠密图用朴素版，稀疏图用堆优化版。

算法思想

首先给定起始点和终点，求起始点到终点的最短路径。
Dijkstra算法的做法是：

1. 在所有顶点里找到距离起点最近的点，将它放入集合S。
2. 用这个顶点来更新其它顶点到起点的距离。
3. 重复1,2步，直到所有顶点都在集合S里，此时，终点存的距离就是终点到起点的最短距离。

朴素版Dijkstra例题

ACWING849. Dijkstra求最短路 I
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

AC代码：

#include 
using namespace std;
const int N=520;
int st[N],g[N][N],dist[N];
int n,m;
int Dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;idist[j]||t==-1))
                t=j;
        }
        st[t]=1;
        for(int j=1;j<=n;j++)
        {
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
    }
    if(dist[n]==0x3f3f3f3f)return -1;
    return dist[n];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x,y,z;
    memset(g,0x3f,sizeof g);
    cin>>n>>m;
    while(m--)
    {
        cin>>x>>y>>z;
        g[x][y]=min(g[x][y],z);
    }
    cout< 
核心思想和注意点：
 
朴素版Dijkstra算法用邻接矩阵来存储图
起点到起点的距离初始化为0，其余顶点到起点的距离初始化为无穷大
因为有重边，所以在输入图时要多加一步判断，保证选重边里权重最小的：
 g[x][y]=min(g[x][y],z);
 
ACWING850. Dijkstra求最短路 II
 给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
 
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
 
输入格式
 第一行包含整数 n 和 m。
 
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
 
输出格式
 输出一个整数，表示 1 号点到 n 号点的最短距离。
 
如果路径不存在，则输出 −1。
 
数据范围
 1≤n,m≤1.5×105,
 图中涉及边长均不小于 0，且不超过 10000。
 
输入样例：
 
3 3
1 2 2
2 3 1
1 3 4
 
输出样例：
 
3
 
AC代码：
 
#include 
using namespace std;
typedef pair PII;
const int N = 150010;
int st[N], h[N], e[N], ne[N], dist[N], w[N], idx;
int n, m;
void add(int x, int y, int z)
{
    e[idx] = y;
    ne[idx] = h[x];
    w[idx] = z;
    h[x] = idx++;
}
int Dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    priority_queue, greater> heap;
    heap.push({0, 1});
    while(!heap.empty())
    {
        PII t = heap.top();
        heap.pop();
        int distance = t.first, ver = t.second;
        if(st[ver])
            continue;
        st[ver] = 1;
        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];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x, y, z;
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while(m--)
    {
        cin >> x >> y >> z;
        add(x, y, z);
    }
    cout << Dijkstra() << 'n';
    return 0;
}

 
核心思想和算法：
 
用小根堆来实现算法，比起朴素版，寻找距离最短的结点的效率快了
要用pair来存储图的结点，pair记载了两个信息，距离和顶点编号。距离用来堆排序，顶点编号用来取结点时识别结点。
pair的first一定是距离，因为堆排序是按距离排的。
if(st[ver]) continue;这段代码的含义是，可能会有两个结点a和b同时指向c，那么在对a和b进行更新时，就会把c二次入堆，可我们只需要对c更新一次就够了，所以在第二次见到c时就无须进行for循环了，直接在算法中段停止即可。
由于邻接表和堆的特点，在输入图时无需考虑重边问题，算法中会自动选择距离小的边放入堆中
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5610592.html