update:2023.07.19 更新了堆优化版本的 Dijkstra
update:2023.09.21 更新了时间复杂度讨论并修改了堆优化 Dij

Dijkstra

什么是Dijkstra

Dijkstra采用了贪心的策略。

在一张连通图中，我们将点分类为已知点和未知点。

什么是已知点？就是已经遍历过的，例如原点（出发点）就是一个已知点。

什么是未知点？顾名思义，就是未遍历到的点（除了已知点，剩下的就是未知点）

理解贪心策略

这里举一个简单的栗子：

夏福要去 supermarket，他面前可以选择 3 个商店：

1.壹加壹超市，据夏福 1000m

2.美宜佳商店，据夏福 500m

3.711超市，据夏福 200m

他该去哪个超市呢？

这里很容易看出来，肯定是选择第 3 种方案。

没错，这就是从夏福（原点）到超市（终点）的最短路径。也就是贪心策略。

思考实现代码

因为贪心只能保证局部最优，不能保证全局最优，所以我们还是需要去遍历，但是我们可以缩小遍历的范围。

假想现在从已知点可以到达三个中转站，最后都可以到终点。

那么从起点到终点的路径就是：起点到中转站的路径 + 中转站到终点的路径

我们想让起点到中转站的距离尽可能的小，那肯定是选择据起点最近的中转站作为新的起点（新的已知点）

我们就可以把那个点当作起点，继续找最短路径就好了。

原来那个点怎么办？

丢进垃圾桶里~

代码实现

题目：输出从 $s$ 到 $t$ 的最短路，并换行输出最短路径 Input

Output

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91


#include <bits/stdc++.h>
using namespace std;

int n, m;
int edge[505][505];
int ss, tt;
bool vis[505];
pair<int, int> dis[505]; // 相当于一个变量里有两个成员：一个是距离，另一个是数组下标所连接的点
vector<int> q[505];
vector<int> ans;

bool cmp(int a, int b)
{
    return a < b;
}

int main()
{
    scanf("%d%d", &n, &m); // 输入点的个数n，边的数量m

    for (int i = 1; i <= m; i++)
    {
        int l, r, v;
        scanf("%d%d%d", &l, &r, &v); // 输入边的信息：边连接的两个点l、r，和边的权值v

        edge[l][r] = v; // 表示从l到r这个点的权值是v
    /* 因为这个代码是有向图的最短路问题，如果是无向图的话应该再加上下面这行代码：

    edge[r][l] = v;

    这个表示r到l的路径边权是v */
    }

    scanf("%d%d", &ss, &tt); // 输入ss（原点）和tt（终点），这个代码是输出从ss到tt的最短路径

    for (int i = 1; i <= n; i++)
        dis[i].first = 1e9; // 初始化从原点到第i个点的路径全部为正无穷（这里只要数据够大就行了）
    fill(vis, vis + n + 1, 0); // 初始化所有的点都没被访问过
    dis[ss].first = 0; // 从原点到原点的距离肯定是0
    dis[ss].second = ss; // 默认原点和原点相连

    for (int i = 1; i <= n; i++)
    {
        int tmp = -1; // 存储下标的临时变量

        for (int j = 1; j <= n; j++)
        {
            if (!vis[j] && (tmp == -1 || dis[j] < dis[tmp]))
            {
        // 只要 (j未被访问过) 并且只要达到 [(tmp未赋值) 或 (找到离i点有更近的点)] 的条件之一
                tmp = j;
        // tmp就赋值为j
            }
        }

        vis[tmp] = 1; // 完事之后，备注tmp已经被访问过了，丢进**垃～圾～桶～**里
        for (int j = 1; j <= n; j++)
        {
            if (dis[tmp].first + edge[tmp][j] < dis[j].first && tmp != j && edge[tmp][j])
            {
        /*
          如果 (到tmp的距离 + tmp到j的距离 < 原来到j的距离)
          并且
          (tmp和j不是同一个点)
          并且
          (tmp到j的距离不是0)
          的话
            */
        dis[j].first = dis[tmp].first + edge[tmp][j];
                dis[j].second = tmp;
        // 到j的距离重新赋值，与j相邻的点就变为tmp
            }
        }
    }

    printf("%d\n", dis[tt].first); // 输出终点的距离

    int temp = tt;
    while (dis[temp].second != ss) // 只要与temp这个临时变量相邻的不是起点，就进行
    {
        ans.push_back(temp); // 把temp存储进ans数组里
        temp = dis[temp].second; // temp就重新赋值
    }
    ans.push_back(temp); // 最后一个点会跳出循环，所以要存储
    ans.push_back(ss); // 把原点也放进去

    for (int i = ans.size() - 1; i >= 0; i--)
    {
        printf("%d ", ans[i]); // 倒过来输出就行了
    }
}

注意：

Dijkstra 采用的是贪心的策略，所以遇上有负边的图时，它就会陷入自环中。

SPFA

什么是 SPFA

相对 Dijkstra 来讲，在随机生成数据中，会比Dijkstra会更快一点。

它是基于邻接表的基础写的。

理解邻接表

在一张连通图中，一个点并不总是只连着一个点。

举个粒子：

小 A 家处于十字路口，可以从小 A 家到小 B 家、小 C 家、小 D 家等多个 good friends 的家。

而对于小 A 家的邻接表就是： $B\to C\to D$

代码实现

题目：给一堆数据，输出 $1$ 到 $n$ 的最短路 Input

Output

1

66

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69


#include <bits/stdc++.h>
using namespace std;

int n, m;
struct edge
{
    int s, e, val;
};
int maxx = INT_MIN;
int step;
vector<edge> b[5005];
queue<int> q;
int dis[5005];
bool vis[5005];

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i++)
    {
        int x, y, v;
        edge ee;
        scanf("%d%d%d", &x, &y, &v);

        ee.s = x, ee.e = y, ee.val = v;

        b[x].push_back(ee); // 存储x的邻接表
    }

    fill(dis, dis + n + 1, 1e9); // 初始化路径全部为正无穷（数据足够大就行）

    q.push(1);
    dis[1] = 0;
    vis[1] = 1;
    while (!q.empty())
    { // STL宽搜
        step++;
        if (step > m)
        { // 出现负环，直接退出
            printf("No Solution");
            return 0;
        }

        int u = q.front();
        q.pop();

        for (int i = 0; i < b[u].size(); i++)
        { // 对于当前这个u点的邻接点
            int vv = b[u][i].val;
            int en = b[u][i].e;

            if (dis[u] + vv < dis[en])
            { // 如果 (到u点距离) + (从u点到它的邻接点的距离) < (原来的到en的距离)
                dis[en] = dis[u] + vv;

                if (!vis[en])
                { // 在压入队列之前进行标记，否则会陷入死循环
                    vis[en] = 1;
                    q.push(en);
                }
            }
        }

        vis[u] = 0; // 标记这个点《 免 费 》了（free这个点）
    }

    printf("%d", dis[n]);
}

Floyd

什么是 Floyd

就是运用枚举中间点进行松弛（专业术语，指令这个点距离最小）每个点的距离。

理解枚举中间点

还是举个梨子：

小 A 和小 B 有一定的亲密度，为了使他们的亲密度更近，需要一个中介来帮忙。通过中介的帮忙，他们是否能提升之间的亲密度呢？所以我们就枚举一下。

代码实现

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


for (int k = 1; k <= n; k++)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i != j && i != k && j != k)
            {
                if (dis[i][k] + dis[k][j] < dis[i][j])
                {
                    dis[i][j] = dis[i][k] + dis[k][j];
                    // 这样写的话，无论是有向图还是无向图都成立
                }
            }
        }
    }
}

但是这个时间复杂度是

$O(n^3)$

《没逝，就慢了亿点点》

堆优化Dijkstra

思想

因为Dijkstra类似于贪心的策略，每次都选择边权最小的边。如果我们用小根堆来维护呢？

是的，所以堆优化 Dijkstra 用到了优先队列优化。

因为曾有“关于 SPFA ——他死了”的一说，所以这个就很吃香。更好的是，这个和 SPFA 代码实现很像，所以直接入手是很容易的。

代码实现

code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68


#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back

const int MAXN=500+5,MAXM=500+5,INF=0x3f3f3f3f3f3f3f3f;

int n,m;
int dis[MAXN];
bool vis[MAXN];
int su,en[MAXM<<1],vl[MAXM<<1],hd[MAXN],lt[MAXM<<1];
struct node
{
    int id,dis;
    bool operator>(const node &T)const
    {
        return dis>T.dis;
    }
};

void add(int u,int v,int w)
{
    en[++su]=v,vl[su]=w,lt[su]=hd[u],hd[u]=su;
}

int Dij()
{
    priority_queue<node,vector<node>,greater<node>> q;
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0,vis[1]=1;
    q.push({1,0});
    while(!q.empty())
    {
        int u=q.top().id;q.pop();
        for(int i=hd[u];i;i=lt[i])
        {
            int v=en[i],w=vl[i];
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push({v,dis[v]});
                }
            }
        }
        vis[u]=0;
    }
    if(dis[n]==INF)
        return -1;
    return dis[n];
}

signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w),add(v,u,w);
    }
    printf("%lld\n",Dij());
    return 0;
}

时间复杂度讨论

堆优化 Dij：$O(m\log m)$
朴素 Dij：$O(n^2)$ SPFA：$O(nm)$（最坏情况） Floyd：$O(n^3)$

一般来说，无负边权就选择 Dij，对于是否采用堆优化，取决于图的稀疏程度。

关于 SPFA……