首页 Data Structure

Dijkstra 算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径

定义：

  • 代价：F(n) = g(n)
  • g (n) ：从起点到节点 n 的代价（距离）
  • open list ：存放 当前可到达、且未确定最小代价路径的节点
  • closed list ：存放 已经找到最小代价路径的节点

流程：

  • 从起点开始逐步扩展，每一步为一个节点找到代价最小的路径，即：
    • 从 open list 选择代价最小的节点，将其收录到 closed list
    • 遍历新收录节点的所有可访问邻节点，更新代价

最优性证明（为什么被收录的节点已经找到代价最小的路径？）：反证法

特性：

  • 完备性：如果在起始点和目标点之间有路径解存在，就一定可以得到解；如果得不到解，就一定说明没有解存在
  • 最优性：对于某个评价指标（一般为路径的长度），规划得到的路径是最优的

算法：

将起点放入 open list

执行循环：

- 如果 open list 为空：搜索失败，结束
- 取 open list 中代价（即，g(n)）最小的节点（记作 Node1），将其放入 closed list
- 如果节点 Node1 为终点：找到目标路径，结束
- 遍历节点 Node1 的（不在 closed list 中的）邻接节点
    - 记当前遍历的邻接节点为 Node2
    - 如果节点 Node2 在 open list 中：更新节点 Node2 的代价
    - 如果节点 Node2 在 open list 中：计算节点 Node2 的代价，并将其加入 open list

待循环结束，即得到从起点到终点的代价最小路径

# 朴素 Dijkstra

# 邻接矩阵法

采用邻接矩阵 edges 存储边的有关信息，其中，edges [i][j] 表示 i 到 j 的代价，若 edges [i][j] == INT_MAX ，则表示不存在由节点 i 指向节点 j 的边

/*
@param:
    edges: 邻接矩阵
    n: 节点数
    start: 起始点
@return: 
    起始点到其他点的最小代价
*/
vector<int> dijkstra(vector<vector<int>>& edges, int n, int start) {
    vector<int> dist(n, INT_MAX);     // dist[i] 表示 start 到 i 的最小代价
    dist[start] = 0;                  // start 到自身的代价为 0
    vector<int> closedlist(n, 0);     // closedlist[i] 表示 i 是否在 closed list 中

    for (int i = 0; i < n; ++i) {     // 从起点开始逐步扩展，每一步为一个节点找到代价最小的路径
        int idx = 0;                  // 不在 closed list 中的、代价最小的节点
        for (int j = 0; j < n; ++j) {
            if (!closedlist[j] && dist[j] <= dist[idx]) {
                idx = j;
            }
        }
        closedlist[idx] = 1;          // 将代价最小的节点 idx 添加到 closed list
        for (int j = 0; j < n; ++j) { // 更新 idx 邻居节点的代价
            if (!closedlist[j] && edges[idx][j] < INT_MAX) {
                dist[j] = min(dist[j], dist[idx] + edges[idx][j]);
            }
        }
    }

    return dist;
}

# 邻接表法

采用 链式前向星（用数组模拟实现的链表，也就是静态链表）作为邻接表

结构体数组 edges 存储所有边：edges [i] 表示第 i 条边

  • edges [i].to 表示第 i 条边的终点
  • edges [i].next 表示与第 i 条边同起点的下一条边的编号
  • edges [i].w 表示第 i 条边的权值

数组 head 存储顶点的第一条边：head [i] 表示以 i 为起点的第一条边（编号最大的边）的编号

/*
@param:
    edges: 静态链表
    head: 节点数组
    n: 节点数
    start: 起始点
@return: 
    起始点到其他点的最小代价
*/
vector<int> dijkstra(Edge& edges[], vector<int>& head, int n, int start) {
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;
    vector<int> closedlist(n, 0);

    for (int i = 0; i < n; ++i) {
        int idx = 0;
        for (int j = 0; j < n; ++j) {
            if (!closedlist[j] && dist[j] <= dist[idx]) {
                idx = j;
            }
        }
        closedlist[idx] = 1;
        for (int j = head[idx]; j != -1; j = edges[j].next) { // 遍历链式前向星
            dist[edges[j].to] = min(dist[edges[j].to], dist[idx] + edges[j].w);
        }
    }

    return dist;
}

# 堆优化 Dijkstra

可以使用堆（优先级队列）来查找 open list 中的代价最小的节点 idx

定义一个小顶堆：由于 pair<typeA, typeB> 排序时会默认按照 typeA 排序，应将起点到节点的代价作为 typeA 、将节点的编号作为 typeB ，以便每次可以从堆中取出代价最小的节点

typedef pair<int, int> pii; // 分别存储代价和节点编号
priority_queue<pii, vector<pii>, greater<pii>> pq; // 小顶堆

priority_queue 位于 <queue> 头文件， pair 位于 <utility> 头文件

# 邻接矩阵法

当探索到一个代价最小的节点 idx 时，会遍历 idx 的邻居节点 i ，如果 dist [idx] + edges [idx][i] < dist [i] ，则需更新节点 i 的代价为 dist [idx] + edges [idx][i]

注意，即便堆中可能已经有 {xx, i} 存在，但由于无法对堆进行寻址访问，故而无法直接将堆中已有的 {xx, i} 更新为

因此，我们采用的策略是：

  • 更新 dist [i] 为 dist [idx] + edges [idx][i]
  • 将 {dist [i], i} 添加到堆（此时，{dist [i], i} 与 {xx, i} 都存在于堆中，但由于 dist [i] < xx ，{dist [i], i} 优先级高于 {xx, i}，因此该操作也等效于更新了堆中的 {xx, i} ）
/*
@param:
    edges: 邻接矩阵
    n: 节点数
    start: 起始点
@return: 
    起始点到其他点的最小代价
*/
vector<int> Dijkstra(vector<vector<int>>& edges, int n, int start) {
    vector<int> dist(n, INT_MAX);

    typedef pair<int, int> pii;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    
    dist[start] = 0;
    pq.emplace(make_pair(0, start));
    
    while (!pq.empty()) {
        int idx = pq.top().second;
        pq.pop();
        for (int i = 0; i < n; ++i) {
            if (edges[idx][i] < INT_MAX) {
                int cost = dist[idx] + edges[idx][i];
                if (cost < dist[i]) {
                    dist[i] = cost;                 // 实时维护 dist 数组，记录当前搜索到的节点 i 的最小代价
                    pq.emplace(make_pair(cost, i)); // 可能已经有 {val, i} 在堆中了，但是 val 必然大于 cost
                }
            }
        }
    }

    return dist;
}

# 邻接表法

堆优化也可以采用链式前向星结构

/*
@param:
    edges: 静态链表
    head: 节点数组
    n: 节点数
    start: 起始点
@return: 
    起始点到其他点的最小代价
*/
vector<int> dijkstra(Edge& edges[], vector<int>& head, int n, int start) {
    vector<int> dist(n, INT_MAX);

    typedef pair<int, int> pii;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    
    dist[start] = 0;
    pq.emplace(make_pair(0, start));
    
    while (!pq.empty()) {
        int idx = pq.top().second;
        pq.pop();
        for (int i = head[idx]; i != -1; i = edges[i].next) {
            int cost = dist[idx] + edges[i].w;
            if (cost < dist[edges[i].to]) {
                dist[edges[i].to] = cost;
                pq.emplace(make_pair(cost, edges[i].to));
            }
        }
    }

    return dist;
}

# 复杂度分析

设图中的节点数为 nn ，边数为 mm ，其中 n≤mn \le m

时间复杂度：

  • 朴素 Dijkstra 算法：O(n2)O(n^2)
  • 堆优化的 Dijkstra 算法：O((n+m)log⁡n)O((n + m) \log{n})

空间复杂度：

  • 邻接矩阵法：O(n2)O(n^2)
  • 邻接表法：O(m)O(m)

堆优化的时间复杂度优于朴素算法

邻接表法的空间复杂度优于邻接矩阵法

参考：

  • 最短路径问题 — Dijkstra 算法最详解
  • Dijkstra 算法（附案例详解）
  • Dijkstra 算法的 C++ 实现
  • Dijkstra 算法时间复杂度分析
阅读次数 次