改進迪杰斯特拉算法（dijkstra）：輸出所有最短路徑

對于權值非負的圖求解單源最短路徑，第一想法是使用dijkstra算法。最短路徑問題是滿足最優(yōu)子結構的：父問題一定會使用子問題的最優(yōu)解。問題在于子問題的計算次序。dijkstra算法思想建立在我們?yōu)闊o負權圖定義的子問題計算順序基礎上：即離源點最近點不會變成其他問題的子問題，其他問題只能成為他的子問題。

?本次實驗在實現dijkstra算法的基礎上：

• 構建基于鄰接表的圖類：Graph.class，便于以后實驗復用。
• 此外加入了優(yōu)先隊列進行優(yōu)化
• 不僅實現對最優(yōu)解（最短路徑）的記錄而且對所有的最優(yōu)解（所有的最短路徑）進行輸出。

本次實現額外實現部分：

• 實現基于鄰接表的Graph數據結構
• 堆優(yōu)化：將時間復雜度優(yōu)化到$nlg(n)$
• 輸出【所有的最短路徑】：需要花費額外的時間復雜度（一般的dijkstra不需要輸出所有的最短路徑，只需要輸出一條，本實驗輸出了所有的最短路徑）

程序如下：

//
// Created by BlancheSun on 2022/4/10.
//

#include<iostream>
#include<algorithm>
#include <vector>
#include <queue>

using namespace std;

class ArcNode{
public:
    int adjvec;
    double weight;
    ArcNode(int adjvec, double weight) : adjvec(adjvec), weight(weight){};
    ArcNode() {};
    friend bool operator<(const ArcNode& arc1, const ArcNode& arc2) {
        return arc1.weight > arc2.weight;
    }
};

class Graph{
private:
    int vexnum; // 頂點數
    int arcnum; // 邊數
    vector<vector<ArcNode>> arcList;   // 矩陣存儲結點之間的連接關系
public:
    Graph(int vexnum, int arcnum);
    Graph();
    void add_edge(int start, int end, double weight);
    void dijkstra(int source, int target);
    void recordShortestPath(vector<vector<int>>& pre, int target, vector<vector<int>>& path, vector<int> temp_path);
    void printAllPath(vector<vector<int>>& path, vector<double>& dis, int source, int target);
};

void Graph::add_edge(int start, int end, double weight){
    arcList[start].push_back(ArcNode(end, weight));
    arcList[end].push_back(ArcNode(start, weight));
}

void Graph::dijkstra(int source, int target) {
    // 初始化操作
    int n = this->vexnum;
    int inf = 99999.0;
    vector<double> dis(n, inf);
    dis[source] = 0;
    vector<vector<int>> pre(n,vector<int>(0));
    priority_queue<ArcNode> nodeQueue;
    nodeQueue.push(ArcNode(source, 0));

    // 隊列非空時進行檢索
    while(!nodeQueue.empty()) {
        int node = nodeQueue.top().adjvec;  // 獲得目前隊列中距離源點最近的結點
        double weight = nodeQueue.top().weight;  // 或者寫成 weight = nodeQueue.top().weight
        nodeQueue.pop();    // 取出隊列中的元素

        if(node == 3||node == 5) {
            int m = 1;
        }
        // 從該結點出發(fā)，更新該結點能直接相連的結點
        for(int i = 0; i < arcList[node].size(); i++) {
            int v = arcList[node][i].adjvec;
            if (weight + arcList[node][i].weight < dis[v]) {    // 越界了！
                dis[v] = weight + arcList[node][i].weight;
                pre[v] = {node};                          // 記錄上一步的結點
                nodeQueue.push(ArcNode(v, dis[v]));
            }else if(weight + arcList[node][i].weight == dis[v]) {
                pre[v].push_back(node);
            }
        }
    }
    vector<vector<int>> path;    // 初始大小的為0,
    vector<int> temp_path;
    recordShortestPath(pre, target, path, temp_path);   // 運行后path_index數值即為路徑條數，不用加一，程序中已經加一
    printAllPath(path, dis, source, target);

}

Graph::Graph(int vexnum, int arcnum) : vexnum(vexnum), arcnum(arcnum) {
    // 做容量的初始化
    vector<vector<ArcNode>> V(vexnum, vector<ArcNode>());
    this->arcList = V;
}

Graph::Graph() {}

/** 第k條路徑的記錄 **/
void Graph::recordShortestPath(vector<vector<int>> &pre, int target, vector<vector<int>>& path, vector<int> temp_path) {
    vector<int> now_pre = pre[target];  // 獲得當前節(jié)點的前驅結點集合
    temp_path.push_back(target);
    if(now_pre.empty()) {   // 沒有前驅結點
        path.push_back(temp_path);
        return;
    }
    // 不為空，那么深搜前驅結點，得到路徑
    for(int i = 0; i < now_pre.size(); i++) {
        int target2 = now_pre[i];   // 集合中的一個點
        recordShortestPath(pre, target2, path, temp_path);
    }
}

/** 打印所有的路徑 **/
void Graph::printAllPath(vector<vector<int>> &path, vector<double>& dis, int source, int target) {
    cout << "The shortest path(es) from node " << source << " to node " << target << " are/is as follows: " << endl;
    int k = path.size();    // 路徑的條數
    for(int i = 0; i<k; i++) {
        cout << "Path" << i << ": " ;
        for(int j = path[i].size()-1; j > 0 ; j--) {
            cout << path[i][j] << " -> ";
        }
        cout << path[i][0] << endl;
    }
    cout << "The length of path(es) is " << dis[target] <<endl;
}

int main() {
	// 多條最短路徑的測試
    Graph graph = Graph(9, 14); // 9個頂點，14條邊

    // 邊的添加
    graph.add_edge(0,1,1);
    graph.add_edge(0,7,8);
    graph.add_edge(1,2,8);
    graph.add_edge(1,7,11);
    graph.add_edge(2,3,3);
    graph.add_edge(2,5,4);
    graph.add_edge(2,8,2);
    graph.add_edge(3,4,9);
    graph.add_edge(3,5,1);
    graph.add_edge(4,5,10);
    graph.add_edge(5,6,2);
    graph.add_edge(6,7,1);
    graph.add_edge(6,8,6);
    graph.add_edge(7,8,7);

    int source = 0, target = 4;
    graph.dijkstra(source, target);
    
//    Graph graph = Graph(16, 30); // 16個頂點，30條邊
//
//    // 邊的添加
//    graph.add_edge(0,2,3);
//    graph.add_edge(1,3,1);
//    graph.add_edge(1,4,3);
//    graph.add_edge(1,5,6);
//    graph.add_edge(2,4,8);
//    graph.add_edge(2,5,7);
//    graph.add_edge(2,6,6);
//    graph.add_edge(3,7,6);
//    graph.add_edge(3,8,8);
//    graph.add_edge(4,7,3);
//    graph.add_edge(4,8,5);
//    graph.add_edge(5,8,3);
//    graph.add_edge(5,9,3);
//    graph.add_edge(6,8,8);
//    graph.add_edge(6,9,4);
//    graph.add_edge(7,10,2);
//    graph.add_edge(7,11,2);
//    graph.add_edge(8,11,1);
//    graph.add_edge(8,12,2);
//    graph.add_edge(9,11,3);
//    graph.add_edge(9,12,3);
//    graph.add_edge(10,13,3);
//    graph.add_edge(10,14,5);
//    graph.add_edge(11,13,5);
//    graph.add_edge(11,14,2);
//    graph.add_edge(12,13,6);
//    graph.add_edge(12,14,6);
//    graph.add_edge(13,15,4);
//    graph.add_edge(14,15,3);
//
//
//    // 求解最短路徑
//    int source = 0, target = 15;
//    graph.dijkstra(source, target);

    return 0;
}

以下圖為例進行執(zhí)行

結果如下：可見所有的最短路徑都被輸出

1. 基于鄰接表的Graph

? 基礎的鄰接矩陣也能作為dijkstra算法的數據結構，但是對于稀疏圖或者結點很多的情況下輸入數據較為復雜且容易超出內存。本次實驗使用鄰接表實現圖的數據結構，主要設置如下：

• ArcNode.class：鄰接表的表結點。含有表結點的終點編號adjvec和邊權重weight兩個屬性。

• vector<vector<ArcNode>> ArcList：

  • ArcList[i]表示結點i為起點的所有表結點的集合

• Graph.class：

  含有三個屬性：

  • vexnum：結點數
  • arcnum：邊數
  • vector<vector<ArcNode>> ArcList：鄰接表

  含有四個方法：

  • add_edge(int start, int end)：向鄰接表中增加表結點

  • dijkstra(int source, int target)：計算最短路徑和所有結點的前驅結點集合，以求得所有最短路徑

  • recordShortestPath(vector<vector<int>> &pre, vector<vector<int>>& path：根據dijksra中的前驅結點集合pre，進行深度優(yōu)先搜索，得到所有的最短路徑，存入path數組中。

  • printAllPath(vector<vector<int>> &path)：打印所有的最短路徑

2 基本算法思路說明與堆優(yōu)化

（1）基本思路

dikstra算法的核心過程很簡單，主要特點是使用廣度優(yōu)先搜索。算法主要過程如下：

• 初始化：
  • 集合初始化：設置已松弛集合$T=?$，和未松弛集合 U = { s 0 , s 1 . . . , s n } U = \{s_0,s_1...,s_n\} U={s0?,s1?...,sn?}全部n個結點。
  • 距離數組初始化：設置有大小為結點個數n的距離數組$vector<int>dis(n,+\infty )$，另外將$dis[s_0]$初始化為0。
• 循環(huán)n輪：每次擴展擴展使用不在集合$T$中（在集合$U$中），且距離源點$s_0$最近的結點$s_k$對所有與$s_k$直接相聯(lián)的結點$s_j$進行松弛，第一輪時即使用$s_0$進行松弛。松弛條件為：

$$\{\begin{array}{l}visited[s_j]==false:s_j為被用來松弛過\\ dis[s_k]+weight(s_k,s_j)<dis[s_j]\end{array}$$

? 滿足條件即更新$dis[s_j]=dis[s_k]+weight(s_k,s_j)$。更新完后將$s_k$加入集合T，從U中移出$s_k$。

? 從動態(tài)規(guī)劃的角度看，上式也可以理解成動態(tài)規(guī)劃的遞推式。

• 循環(huán)結束：每個結點都被加入$T$，此時的$dis[n]$即為最短距離。

（2）堆優(yōu)化

在（1）的步驟二循環(huán)n輪中，每次循環(huán)需要尋找距離源點$s_0$最近的結點。若是采取循環(huán)掃描一遍的過程，那么dijkstra算法的時間復雜度將會為$O(n^2)$，仔細分析，該過程尋找最近距離的過程有下面的特點：

• 集合大小是動態(tài)變化的結點
• 每次從集合中尋找的距離最小的元素，不需要所有的元素有序

符合這樣的特點我們可以用堆進行優(yōu)化。即：

• ① 將遍歷$dis[s_k]$尋找最小值的過程使用一個優(yōu)先隊列$nodeQueue$的top()和pop()操作代替。同時$visted$數組變得不再需要，因為該結點被$pop()$，下輪更新隊列中將不會存在該結點。
• ② 每次對松弛對$dis[v]$進行操作時，同時需要向優(yōu)先隊列中減小該結點的$weight$。

3 實現多條最短路徑記錄

3.5.3.1 路徑的記錄

如果只需要記錄一條最短路徑，那么我們在進行松弛操作后用一個數組$pre[n]$記住用于松弛該結點的$s_k$即可。即：
$$pre[s_j]=s_k$$
我們這里實現了多條最短路徑的輸出，一維數組不再能滿足我們的要求，我們需要一個二維數組$pre[n][m]$記錄所有的前驅結點。對于一個結點編號為$i$的結點，其所有的前驅為$pre[i]$集合中的所有元素。當然，如果最短路徑只有一條，那么$pre[i]$中只有一個元素。

另外，需要存儲多條最短路徑后，在松弛時進行的操作和只輸出一條路徑時不相同：

• 若$dis[s_k]+weight(s_k,s_j)<dis[s_j]$：

  直接將$pre[s_j]$置為$s_k$的編號，然后將隊列中修改$s_j$的權重為$dis[s_k]+weight(s_k,s_j)$，更新$dis[s_j]=dis[s_k]+weight(s_k,s_j)$

• 若$dis[s_k]+weight(s_k,s_j)==dis[s_j]$

  向$pre[s_j]$中增加$s_k$的編號

3.1 路徑的輸出

按照上述的方式進行記錄后，我們最終得到的$pre$數組，為了便于說明，我們給出下面的一個例子：

以圖中的結點4為例，我們給出他的$pre$數組樹：

根據這棵$pre$數組樹，我們能夠通過深度優(yōu)先遍歷的方式得到從結點4開始到源點0的所有的最短路徑。在深搜過程中我們每得到一條路徑就應該將他存在一個二維的$path$數組，每一維存儲一條路徑。在得到所有最短路徑后，遍歷$path$數組的每個元素，每一個元素即是一條路徑的路徑數組，逐條打印出路徑結果即可。文章來源地址http://www.zghlxwxcb.cn/news/detail-403408.html

到了這里，關于dijkstra算法：堆優(yōu)化 + 輸出所有最短路徑（得到所有最優(yōu)解）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！