Dijkstra算法详解（朴素算法+堆优化）

时间：2023-02-05 07:08:41

定义

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算法详解（朴素算法+堆优化）

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为起点求出剩余顶点的最短距离。

Dijkstra算法详解（朴素算法+堆优化）

（PS：黑色空心节点表示U中的节点，绿色空心节点表示S中的节点，绿色实心节点表示当前选中的节点）

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

Dijkstra算法详解（朴素算法+堆优化）

此时，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。

Dijkstra算法详解（朴素算法+堆优化）

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

Dijkstra算法详解（朴素算法+堆优化）

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

Dijkstra算法详解（朴素算法+堆优化）

代码实现

传统实现

类定义

因为每条边携带了权值信息，所以这里使用邻接矩阵来表示图。非邻接节点之间的权值规定为无穷大。出于效率考虑，这里使用一维数组存储邻接矩阵，假设整个图的节点数为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))

标签：

相关文章