Dijkstar（不堆优化）学习笔记

jiangchen1234 · 2023-12-07 23:01:01 · 个人记录

什么是 Dijkstar 算法

所谓 Dijkstar（不堆优化）就是一种能在 \operatorname O(n^{2}) 时间之内解决单源最短路径问题的一种算法。

那啥是单源最短路径问题？

单源最短路径问题（Single Source Shortest Path，SSSP 问题）是说，给定一张有向图 G = (V,E)，V 是点集，E 是边集，\left\vert V \right\vert = n)，\left\vert E \right\vert = m)，节点以 [1.n] 之间的连接整数编号，(x,y,z) 描述一条从 x 出发，到达 y，长度为 z 的有向图。设 1 号点为起点，求长度为 n 的数组 dish，其中 dish_{i} 表示从起点 1 到节点 i 的最短路径的长度。

摘自算法竞赛进阶指南。

如何实现 Dijkstar 算法

Dijkstar 算法的流程如下：

初始化 dish_{1} = 0，其余节点的 dish 值为无穷大。
找出一个为被标记的，dish_{x} 最小的节点 x，然后标记节点 x。
扫描节点 x 的所有出边 (x,y,z)，若 dish_{y} > dish_{x} + z，则使用 dish_{x} + z 更新 dish_{j}
重复上述 2 \sim 3 两个步骤，直至所有节点都被标记。

Dijkstar 算法基于贪心思想，它只适用于所有边长度都是非负数的图。当边长 z 都是非负数时，全局最小值不可能再被其他节点更新，故在第 1 步时选出来的节点 x 必然满足：dist_{x} 已经是起点到 x 的最短路径。我们不断选择全局最小值进行标记和扩展，最终可得到起点 1 到每个节点的最短路径长度。

摘自算法竞赛进阶指南。

其中 2 \sim 3 两个步骤可以叫做松弛。

接下来上代码（假设 n \le 3000）：

#pragma comment(linker,"/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define int long long
#define il inline
#define rg register
#define F(i,l,r) for(int i=l,i##end=r;i<=i##end;++i)
#define G(i,l,r) for(int i=l,i##end=r;i>=i##end;--i)
#define endl '\n'
il int read() {
    int s = 0,w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-')w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
    return s * w;
}
il void write(int x) {
    if(0<=x&&x<=9) {
        putchar(x + '0');
        return ;
    }
    write(x/10);
    putchar(x%10+'0');
}
il int max(int a,int b) {
    return a > b ? a : b;
}
il int min(int a,int b) {
    return a < b ? a : b;
}
using namespace std;
int t;
int e[3010][3010],dis[3010],n,m,vis[3010];//e 用来存边，dis 是文中 dish 的简称,vis 用来存有无标记
il void read_in() { //读入
    n = read(),m = read();//n 个点，m 条边
    for(rg int i(1); i <= n; ++i) {
        e[i][i] = 0;
    }
    for(rg int i(1); i <= m; ++i) {
        int x = read(),y = read(),z = read();
        e[x][y] = min(e[x][y],z);
    }
}
il void init() { //初始化
    memset(e,0x3f,sizeof(e));// e 数组初值为无穷大
    memset(dis,0x3f,sizeof(dis));// dis 数组初值为无穷大
    memset(vis,0,sizeof(vis));// 节点标记
}
il void dijkstar() { //Dijkstar
    dis[1] = 0;
    for(rg int i(1); i <= n - 1; ++i) { //一个点以知，故要松弛 n - 1 次
        int u = 0;//dis 中未标记的最小的节点
        for(rg int j(1); j <= n; ++j) {
            if(!vis[j] && (u == 0 || dis[j] < dis[u])) u = j;
        }
        vis[u] = 1;//标记
        for(rg int j(1); j <= n; ++j) { //更新
            dis[j] = min(dis[j],dis[u] + e[u][j]);
        }
    }
}
il void print() { //输出
    for(rg int i(1);i <= n;++i){
        cout<<dis[i]<<endl;
    }
}
il void solve() {
    init();
    read_in();
    dijkstar();
    print();
}
signed main() {
    ios::sync_with_stdio(false);
    t = 1;
    while(t--) {
        solve();
    }
    return 0;
}
/*
4 3
1 3 1
3 2 1
2 4 3
*/

例题 P1529 [USACO2.4] 回家 Bessie Come Home

题目描述

现在是晚餐时间，而母牛们在外面分散的牧场中。

Farmer John 按响了电铃，所以她们开始向谷仓走去。你的工作是要指出哪只母牛会最先到达谷仓（在给出的测试数据中，总会有且只有一只最快的母牛）。在挤奶的时候（晚餐前），每只母牛都在她自己的牧场上，一些牧场上可能没有母牛。

每个牧场由一条条道路和一个或多个牧场连接（可能包括自己）。有时，两个牧场（可能是字母相同的）之间会有超过一条道路相连。至少有一个牧场和谷仓之间有道路连接。因此，所有的母牛最后都能到达谷仓，并且母牛总是走最短的路径。当然，母牛能向着任意一方向前进，并且她们以相同的速度前进。牧场被标记为 \texttt{a} \ldots \texttt{z} 和 \texttt{A} \ldots \texttt{Y}，在用大写字母表示的牧场中有一只母牛，小写字母中则没有。谷仓的标记是 \texttt{Z}，注意没有母牛在谷仓中。

注意 \texttt{m} 和 \texttt{M} 不是同一个牧场。

输入格式

第一行一个整数 P（1\leq P \leq 10^4），表示连接牧场（谷仓）的道路的数目。

接下来 P 行，每行用空格分开的两个字母和一个正整数：被道路连接牧场的标号和道路的长度（道路长度均不超过 10^3）。

输出格式

单独的一行包含二个项目：最先到达谷仓的母牛所在的牧场的标号，和这只母牛走过的路径的长度。

样例 #1

样例输入 #1

5
A d 6
B d 3
C e 9
d Z 8
e Z 3

样例输出 #1

B 11

提示

翻译来自 NOCOW

USACO 2.4

思路

我们可以把牧场看作一个点，使用 Dijkstar 求最早到达的牧场

代码

//#pragma comment(linker,"/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define int long long
#define il inline
#define rg register
#define F(i,l,r) for(int i=l,i##end=r;i<=i##end;++i)
#define G(i,l,r) for(int i=l,i##end=r;i>=i##end;--i)
#define endl '\n'
il int read() {
    int s = 0,w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-')w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
    return s * w;
}
il void write(int x) {
    if(0<=x&&x<=9) {
        putchar(x + '0');
        return ;
    }
    write(x/10);
    putchar(x%10+'0');
}
il int max(int a,int b) {
    return a > b ? a : b;
}
il int min(int a,int b) {
    return a < b ? a : b;
}
using namespace std;
int t,n;
int e[60][60],dis[60],vis[60];//vis[i] 记录有没有到过点 i，dis[i]为终点到 i 的最短路
il void in(int cnt1,int cnt2,int w) {//加入图
    e[cnt1][cnt2] = min(e[cnt1][cnt2],w);
    e[cnt2][cnt1] = min(e[cnt2][cnt1],w);
}
il void read_in() {//输入
    cin>>n;
    for(rg int i(1); i <= n; ++i) {
        char ch1,ch2;
        int w;
        cin>>ch1>>ch2>>w;
        int cnt1 = 0,cnt2 = 0;
        if('a' <= ch1 && ch1 <= 'z') {
            cnt1 = ch1 - 'a' + 1;
        } else {
            cnt1 = ch1 - 'A' + 27;
        }
        if('a' <= ch2 && ch2 <= 'z') {
            cnt2 = ch2 - 'a' + 1;
        } else {
            cnt2 = ch2 - 'A' + 27;
        }
        in(cnt1,cnt2,w);
    }
}
il void init() {//初始化
    memset(e,0x3f,sizeof(e));
    for(rg int i(0); i <= 52; ++i) {
        dis[i] = 1e9;
    }
}
il void dijkstra() {//Dijkstra
    dis[52] = 0;
    for(rg int i(1); i <= 51; ++i) { //松弛n - 1遍
        int u = 0;//最小点
        for(rg int j(1); j <= 52; ++j) { //找最小点
            if(!vis[j] && (u == 0 || dis[j] < dis[u]))  u = j;
        }
        vis[u] = 1;
        for(rg int j(1); j <= 51; ++j) {
            dis[j] = min(dis[j],dis[u] + e[u][j]);
        }
    }
}
il void print() {//输出
    int ansi = 1e10;
    char ansc = 'A';
    for(rg int i(27); i <= 51; ++i) {
        if(dis[i] < ansi) {
            ansi = dis[i];
            ansc = 'A' + i - 27;
        }
    }
    cout<<ansc<<" "<<ansi<<endl;
}
il void solve() {
    init();
    read_in();
    dijkstra();
    print();
}
signed main() {
    ios::sync_with_stdio(false);
    t = 1;
    while(t--) {
        solve();
    }
    return 0;
}

Dijkstar（不堆优化） 学习笔记