C++

单源最短路径（狄克斯特拉算法）

更新时间 单源最短路径（狄克斯特拉算法）有0条评论

在加权图G=(V,E)中，求给定顶点s,d之间各边权值总和最小的路径，这就是最短路径问题。

这个问题主要分为两类：

  • 单源最短路径：在图G中，求给定顶点s到其他所有顶点di之间的最短路径
  • 全点对间最短路径：在图G中，求“每一对顶点”之间的最短路径

求单源最短路径，其实就是求从起点出发的最短路径生成树的过程。如果顶点s到G的所有顶点都存在路径，那么一定存在一棵以s为根，包含s到G所有顶点最短路径的生成树T。这种树就称为最短路径生成树。

狄克斯特拉算法

解决最短路径生成树问题，就需要用到狄克斯特拉算法。

简单版本的狄克斯特拉算法就是这样的：

设图G=(V,E)所有顶点的集合为V，起点为s，最短路径生成树中包含的顶点集合为S。在各计算步骤中，我们将选出最短路径生成树的边和顶点，并将其添加到S。

对于各顶点i，设仅经由S内的顶点s到i的最短路径成本为d[i]，i在最短路径中的父节点为p[i]

  1. 初始状态下，将S置空。
    • 初始化s的d[s]=0,除此以外的d[i]=∞
  2. 循环进行下述处理，直到S=V为止
    • 从V-S中选出d[u]最小的顶点u
    • 将u添加到S，同时将与u相邻且属于V-S的所有顶点v的值按照下述方式更新
      • if(d[u]+w(u,v)<d[v])
        • d[v] = d[u] + w(u,v)
        • p[v]=u

当上述处理结束后，d数组中记录的就是所有节点到起点的最短路径。

要注意的是，狄克斯特拉算法不能应用于包含负权值的图，具有负权值的图可以使用贝尔-福特算法或者弗洛伊德算法来处理。

题目来自于ALDS1_12_B

输入数据是邻接表的形式表示的，但是我们依然可以使用邻接矩阵的方法来存储他们，毕竟空间还是够的，n的最大值是100

#include <iostream>
#include <string.h>
using namespace std;

#define MAXN 105

#define WHITE 0
#define GRAY 1
#define BLACK 2

const int inf = (1 << 21);

int M[MAXN][MAXN];

int d[MAXN];           //节点的最小权值和
int p[MAXN];           //最短路径生成树上的节点的父节点
int color[MAXN] = {0}; //节点的访问状态
int n;

void dijkstra() //狄克斯特拉算法
{
    d[0] = 0;
    color[0] = GRAY;

    int min_cost;

    while (true)
    {
        min_cost = inf;
        int u = -1;
        for (int i = 0; i < n; ++i) //找当前最小路径生成树以外的，权值最小的边，往那边扩展
        {
            if (color[i] != BLACK && d[i] < min_cost)
            {
                min_cost = d[i];
                u = i;
            }
        }

        if (u == -1)
            break;

        color[u] = BLACK; //当前节点加入最小路径生成树，标记为黑色

        for (int v = 0; v < n; ++v) //对于加入节点u之后的最小路径生成树，将待选节点的权值和算出来。以便下一轮扩展。
        {
            if (color[v] != BLACK && M[u][v] != inf)
            {
                if (d[u] + M[u][v] < d[v])
                {
                    d[v] = d[u] + M[u][v];
                    p[v] = u;
                    color[v] = GRAY;
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            M[i][j] = inf;

    for (int i = 0; i < n; ++i)
        d[i] = inf;

    for (int i = 0; i < n; ++i)
    {
        int u, k;
        cin >> u >> k;
        int v, c;
        for (int j = 0; j < k; ++j)
        {
            cin >> v >> c;
            M[u][v] = c;
        }
    }

    dijkstra();
    
    for (int i = 0; i < n; ++i)
    {
        cout << i << ' ' << d[i] << endl;
    }
}

上面这样子计算单源最短路径，时间复杂度为O(n2)，然后空间复杂度也是n2的。

然后对于 ALDS1_12_C 这道题目，n的范围被扩大到了10000，算一下之后会发现，如果采用上面的算法进行处理的话，一定会超时。这就需要我们降低时间复杂度

要降低空间复杂度的话，可以用邻接表或者链式前向星结合vector来解决，

那么，如何降低时间复杂度呢？

这就需要用到优先级队列。

这里我们用到的优先级队列需要是小根堆。在应用STL的priority_queue之后，剩下的部分其实思路是类似的。直接看代码就好了。

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

#define MAXN 10005
#define INF (1 << 21)
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n;

vector<pair<int, int>> adj[MAXN]; //加权有向图的邻接表表示法

int color[MAXN] = {0};
int d[MAXN];
int p[MAXN]; //最短路径生成树（存储每个节点的父节点）

void dijkstra()
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; //这里面第一个int指的是路径长度，第二个int指的是节点编号

    for (int i = 0; i < n; ++i)
        d[i] = INF;

    d[0] = 0;
    pq.push(make_pair(0, 0));

    color[0] = GRAY;

    while (!pq.empty())
    {
        pair<int, int> f = pq.top();
        pq.pop();

        int u = f.second;
        color[u] = BLACK;

        //取出最小值，如果不是最短路径则忽略
        if (d[u] < f.first)
            continue;

        for (int j = 0; j < adj[u].size(); ++j)
        {
            int v = adj[u][j].first;
            if (color[v] == BLACK)
                continue;

            if (d[v] > d[u] + adj[u][j].second)
            {
                d[v] = d[u] + adj[u][j].second;
                p[v] = u; //建立最短路径生成树
                pq.push(make_pair(d[v], v));
                color[v] = GRAY;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    int u, k, v, c;
    for (int i = 0; i < n; ++i)
    {
        cin >> u >> k;
        for (int j = 0; j < k; ++j)
        {
            cin >> v >> c;
            adj[u].push_back(make_pair(v, c));
        }
    }

    dijkstra();

    for (int i = 0; i < n; ++i)
    {
        cout << i << ' ' << d[i] << endl;
    }
}

分析知，从优先级队列中取出顶点u的时间复杂度为O(|V|log|V|),更新d[v]的时间复杂度为O(|E|log|V|),因此，整体的时间复杂度就是O((|E|+|V|)log|V|)，那么掐指一算，是可以在1s内完成的。

转载请注明原文出处：https://www.longjin666.top/?p=746

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~

你也可能喜欢

发表评论