dijkstra算法详解(朴素算法+堆优化)-编程思维

定义

Dijkstra(读音:/'daɪkstrə/)算法,是用来求解一个边带权图中从某个顶点出发到达其余各个顶点的最短距离的算法。(为表达简便,下文中“起点(源点)到某个顶点的距离”简称为“某个顶点的距离”)

限制条件:各个边的权不能为负。

原理

假设s,v1,v2,...,vn(以下简称P1)为从源点s到vn的最短路,则s,v1,v2,...,vi-1(以下简称P2)也为从源点s到vi-1的最短路。

这点可以用反证法证明,假如P2不是从源点s到vi-1的最短路,那必然存在某两个m、n(1 <= m < n <= i-1),使得在vm和vn之间,存在着某条更短的路径。由于P1只不过是在P2的基础上加上了vi-1到vi的距离,那么P1显然就不是最短路了。如图:

Dijkstra算法利用了这一点,从源点出发,不断地利用已知的最短距离,依次求得剩余顶点的最短距离。因此,这是一个贪心算法。

算法步骤

引入两个集合S和U,S为已求出最短距离的点的集合,U为尚未求出最短距离的点的集合。显然S和U的交集为空,且S与U的并为整个图的所有节点。初始时,S为空,而U包含图的所有节点。初始时,除了起点的距离初始化为0之外,其余所有节点的距离设为无穷大。(这样才能保证能够从起点开始)

不断执行以下步骤,直到S已包含所有的顶点:

  1. 从U中找出距离最小的点,令其为v。
  2. 将v从U移到S。
  3. 对于v的每一个邻接节点v',如果v'属于U,且v的距离加上边v-v'的长度之和小于v'的距离则更新v'的距离。(如果v'的距离为无穷大,那么因为v的距离加上边v-v'的长度之和一定是有限的,所以v'的距离一定会得到更新)

举个例子:

给定下面这张图,以0为起点求出剩余顶点的最短距离。

(PS:黑色空心节点表示U中的节点,绿色空心节点表示S中的节点,绿色实心节点表示当前选中的节点)

首先,S为空,而U包含了所有的节点。在U中的所有节点中,节点0的距离最短,为0。将0移到S,并更新其所有邻接节点的距离。

此时,U包含的节点为1、2、3、4、5、6,其中距离最短的节点为1。1的邻接节点为0、2、3,其中:

  • 节点0已属于S,不做任何处理。
  • 节点1的距离4加上1到2这条边的距离2为6,小于节点2的距离7,因此更新2的距离为6。
  • 节点1的距离4加上1到3这条边的距离10为14,小于节点3的距离无穷大,因此更新3的距离为14。

此时,U中距离最小的顶点为2,同样的方法,更新其邻接节点的距离。

按照上面的步骤一直进行下去,就可以得到所有节点的最小距离:

代码实现

传统实现

类定义

因为每条边携带了权值信息,所以这里使用邻接矩阵来表示图。非邻接节点之间的权值规定为无穷大。出于效率考虑,这里使用一维数组存储邻接矩阵,假设整个图的节点数为n,则节点i和 节点j的边的权值为数组中下标为i*n+j的值。

由于每条边的权值规定不能为负,因此这里用std::size_t(计算机能够表示的最大的无符号整数类型)存储权值。

另外,用16进制的0x3f3f3f3f表示无穷大。这个数在10进制下是109数量级的,这样既可以保证路径长度在一般情况下远远不会达到这么大,也可以确保在进行加法运算的时候不会溢出。

#define INF 0x3f3f3f3f

为了使语义更加明确,使用类型别名表示节点下标,以和其他的整数信息(如权值等)区分开。

using node_t = std::size_t;

因此,整个图类定义如下:

class Graph {
    std::size_t n; // 节点个数
    std::vector<std::size_t> adjMatrix; // 邻接矩阵

public:
    using node_t = std::size_t; // 类型别名,表示节点下标

    Graph(std::size_t n, std::initializer_list<std::size_t> il) : n(n), adjMatrix(il) {} // 构造函数

    std::vector<std::size_t> dijkstra(node_t start); // Dijkstra算法,起点通过入参start指定
};

算法代码

由于一个节点要么属于S,要么属于V,因此我们使用一个bool数组,true表示该节点属于S,false表示该节点属于V。初始时,数组元素全为false。

std::vector<bool> shortest(n, false);

因此,整个算法代码的实现如下:

std::vector<std::size_t> Graph::dijkstra(Graph::node_t start) {

    // shortest数组定义
    std::vector<bool> shortest(n, false);

    // 存储各个顶点距离的数组
    std::vector<node_t> distance(n, INF); // 其余元素初始化为无穷大
    distance[start] = 0; // 起点距离初始化为0

    // 集合U中还剩余多少个节点
    std::size_t left = n;

    // 循环执行以下步骤,直到U中没有节点了
    while (left) {

        // 从U中选出距离最小的节点
        node_t cur = 0;
        std::size_t minDistance = INF;
        for (node_t v = 0; v < n; ++v) {
            if (shortest[v]) continue; // 排除掉已经在S中的节点
            if (distance[v] < minDistance) {
                cur = v;
                minDistance = distance[cur];
            }
        }

        // 将该节点从U移到S
        shortest[cur] = true;
        left--; // 剩余节点数相应减一

        // 更新该节点所有在U中的邻接节点的距离
        for (node_t neighbor = 0; neighbor < n; neighbor++) {
            if (shortest[neighbor]) continue; // 排除S中的节点
            auto dis = adjMatrix[cur * n + neighbor]; // 该节点与邻接节点之间的权值
            if (dis == INF) continue; // 排除不与该节点邻接的节点
            distance[neighbor] = std::min(distance[cur] + dis, distance[neighbor]); // 更新邻接节点的距离
        }
    }
    return distance;
}

测试:

int main() {
    Graph::node_t n = 6;
    Graph::node_t start = 0;
    Graph graph(n, {0, 4, 7, INF, INF, INF,
                    4, 0, 2, 10, INF, INF,
                    7, 2, 0, 2, 3, INF,
                    INF, 10, 2, 0, 5, 8,
                    INF, INF, 3, 5, 0, 4,
                    INF, INF, INF, 8, 4, 0});
    auto distance = graph.dijkstra(start);
    for (Graph::node_t node = 0; node < n; ++node) {
        std::cout << start << "->" << node << ": " << distance[node] << std::endl;
    }
    return 0;
}

输出:

0->0: 0
0->1: 4
0->2: 6
0->3: 8
0->4: 9
0->5: 13

时间复杂度分析

时间复杂度:可以看出,算法代码里面有while循环嵌套着for循环,其中while循环的执行次数为n(left初始化为n,每次循环减一,直到减到0退出循环),for循环的执行次数也为n,因此时间复杂度为O(n2)。

这样的时间复杂度好像不太能令人满意,那么是否可以减少时间成本呢?

答案是可以的。

堆优化

我们发现,每次选出距离最小的点,都需要遍历图中所有的顶点,时间成本为O(n),显然过大。利用优先队列这个数据结构,我们可以将时间成本减少为O(1)。(C++的STL中的优先队列的底层实现默认为完全二叉堆)

要实现这一点,我们首先需要定义一个struct,包含节点下标和距离。同时,我们也需要定义一个operator>重载运算符用来定义比较大小的规则(按照距离值排序)。

struct Node {
    std::size_t index;
    std::size_t distance;

    Node(std::size_t index, std::size_t distance) : index(index), distance(distance) {}

    inline bool operator>(Node another) const {
        return distance > another.distance;
    }
};

类定义

为节省空间和时间,我们改用邻接列表的方式存储图。

class Graph2 {

    struct Node {
        std::size_t index;
        std::size_t distance;

        Node(std::size_t index, std::size_t distance) : index(index), distance(distance) {}

        inline bool operator>(Node another) const {
            return distance > another.distance;
        }
    };

    std::size_t n;
    std::vector<std::list<Node>> adj;

public:
    Graph2(std::initializer_list<std::initializer_list<Node>> ll);

    std::vector<std::size_t> dijkstra(std::size_t start);
};

算法代码

定义一个存储节点的小根堆:

std::priority_queue<Node, std::vector<Node>, std::greater<>> heap;

每次遍历某个节点的邻接节点的时候,更新完其距离就将其扔到堆里,以供下次取距离最小的节点的时候取出。你可能会问,万一同一个节点多次入队怎么办呢?这点不用担心,即便队列里面有多个相同下标的节点,取出的也一定是其中距离最小的那个。而取出之后就在S里面了,因此相同下标的其他节点取出后就可以直接丢弃。所以取出一个节点的时候先要判断其是否处于S中,如果是的话就丢弃。否则就是V中距离最小的节点。

auto cur = heap.top();
heap.pop();
if (shortest[cur.index]) continue;

其余部分相应的更改就是了。

std::vector<std::size_t> Graph2::dijkstra(std::size_t start) {
    std::vector<bool> shortest(n, false);
    std::vector<std::size_t> distance(n, INF);
    distance[start] = 0;
    std::priority_queue<Node, std::vector<Node>, std::greater<>> heap;
    heap.emplace(start, 0); // 初始化

    while (!heap.empty()) {

        // 取出距离最小的顶点
        auto cur = heap.top();
        heap.pop();
        if (shortest[cur.index]) continue; // 如果当前顶点处于S中,就丢弃

        // 将其移入S中
        shortest[cur.index] = true;

        // 更新其邻接节点的距离
        for (auto &neighbor: adj[cur.index]) {
            if (shortest[neighbor.index]) continue;
            if (distance[cur.index] + neighbor.distance < distance[neighbor.index]) {
                distance[neighbor.index] = distance[cur.index] + neighbor.distance;
                heap.emplace(neighbor.index, distance[neighbor.index]);
            }
        }
    }
    return distance;
}

测试:

int main() {
    std::size_t n = 6;
    std::size_t start = 0;
    Graph2 graph({
        {{1, 4},  {2, 7}},
        {{0, 4},  {2, 2}, {3, 10}},
        {{0, 7},  {1, 2}, {3, 2}, {4, 3}},
        {{1, 10}, {2, 2}, {4, 5}, {5, 8}},
        {{2, 3},  {3, 5}, {5, 4}},
        {{3, 8},  {4, 4}}
    });
    auto distance = graph.dijkstra(start);
    for (std::size_t node = 0; node < n; node++) {
        std::cout << start << "->" << node << ": " << distance[node] << std::endl;
    }
    return 0;
}

输出:

0->0: 0
0->1: 4
0->2: 6
0->3: 8
0->4: 9
0->5: 13

时间复杂度分析

时间复杂度:O((n + m) * log(n))。(n为点数,m为边数)

证明:

设每个节点平均拥有的边数为k,即k=m/n。

每一次while循环,执行上述3个步骤,其中:

  • 取出距离最小节点的时间复杂度为O(log(n)),这是因为取出后还要花O(log(n))的时间恢复二叉堆的堆序性。
  • 移动到S中的时间复杂度为O(1)。
  • 更新其邻接节点的距离的时间复杂度为k * O(log(n)) = O(k * log(n)),这是因为放入堆中后还要花O(log(n))的时间恢复二叉堆的堆序性。

而while循环的次数有多少次呢,因为初始时S中有一个节点,每次while循环往S中增加一个节点,当S中有n个节点时停止循环。因此while循环的次数为n-1次,为O(n)量级。

所以,堆优化的Dijkstra算法的时间复杂度为:

O(n) * (O(log(n)) + O(1) + O(k * log(n)))

= O(n) * (k + 1) * O(log(n))

= O(n * k + n) * O(log(n))

= O(m + n) * O(log(n))

= O((n + m) * log(n))

版权声明:本文版权归作者所有,遵循 CC 4.0 BY-SA 许可协议, 转载请注明原文链接
https://www.cnblogs.com/YWT-Real/p/17092649.html

d-编程思维

D - Takahashi Tour https://atcoder.jp/contests/abc213/tasks/abc213_d   思路 图数据结构存储边的关系。 DFS遍历, 对于相邻节点存储使用set。 Code https://atcoder.jp/contests/abc213/submissions

[数据结构] 二分查找 (四种写法)-编程思维

二分查找 二分查找 二分查找(Binary Search)也叫作折半查找,前提是查找的顺序结构是有序的,我们一般在数组上进行二分查找。 二分查找就好像猜数字大小游戏一样。假设要数字目标值属于 [1, 1000] 范围内,当我们猜的数字小于这个目标值时("Too low"),我们需要往大去猜;反之大于这个目标值时("To

d-编程思维

D - Restricted Permutation https://atcoder.jp/contests/abc223/tasks/abc223_d   思路 https://zhuanlan.zhihu.com/p/135094687 利用拓扑排序方法, 先找入度为0的点,建立优先队列,包括: 2 和 3 从2

c-编程思维

C - Don’t be cycle https://atcoder.jp/contests/abc288/tasks/abc288_c   思路 检测出最小环有几个, 然后破掉相同数目的边即可。     检测最小环数目方法:   Code https://atcoder.jp/contests/abc288/su

[数据结构] 树、二叉树、森林的转换-编程思维

树 树的表示方法 双亲表示法 用一组地址连续的存储单元来存放树中的各个节点,每一个节点中有一个数据域和一个指针域,数据域用来存储树中该节点本身的值;另一个指针域用来存储该节点的双亲节点在存储结构中的位置信息。 采用双亲链表存储方式实现查找一个指定节点的双亲节点比较方便,但难以实现查找一个指定节点的孩子节点。 孩子表示

[数据结构] 哈夫曼树-编程思维

哈夫曼树 哈夫曼树简介 给定 N 个权值作为 N 个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树( Huffman Tree )。 哈夫曼树涉及的基本概念 路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子结点之间的通路,称为路径。通路中分支的数目称为路径长度

[数据结构] 根据前中后序遍历中的两种构造二叉树-编程思维

前中后序遍历 前中后序遍历的特点 前序遍历 前序遍历顺序:根节点 -> 左子树 -> 右子树 前序遍历结果:[根节点,[左子树前序遍历结果],[右子树前序遍历结果]] 假如把前序遍历结果存到数组中,数组中的第一个元素就是二叉树根节点的数据,而且还可以知道第二个元素是根节点左孩子的数据,即左子树根节点的数据。

[数据结构] 二分查找 (四种写法)-编程思维

二分查找 二分查找 二分查找(Binary Search)也叫作折半查找,前提是查找的顺序结构是有序的,我们一般在数组上进行二分查找。 二分查找就好像猜数字大小游戏一样。假设要数字目标值属于 [1, 1000] 范围内,当我们猜的数字小于这个目标值时("Too low"),我们需要往大去猜;反之大于这个目标值时("To

[思路笔记] 0112&0114-编程思维

抽象抽象,懒得写了所以好多就打了线段树板子(虽然说确实是板子),凑活着看吧。 0112G.子序列问题 题目大意 给定长度为 \(n\) 的正整数序列 \(A_1,A_2,...,A_n\),定义函数 \(f(l,r)\) 表示不可重集 \(\{A_l,A_{l+1},...,A_r\}\) 的大小,求 \(\sum_{

[数据结构] 哈希表 (开放寻址法+拉链法)-编程思维

哈希表 哈希表的基本概念 哈希表 Hash table 是一种提供快速查找和插入元素的数据结构,也称散列表。哈希表是基于数组的扩展,一般利用数组的下标作为哈希表的键值。 哈希表存储的是由键(key)和值(value)组成的数据。键值 key 是由哈希函数得到的。 哈希函数 除留余数法 除留余数法是一种广泛运用的哈希函数