C++简单实现Dijkstra算法

什么是Dijkstra算法

Dijkstra算法是一种贪心算法，用于解决带权图的单源最短路径问题。它的主要思想是从起点开始，找到距离它最近的节点，将该节点加入已访问的节点中，然后更新其他节点到起点的距离。重复以上步骤，直到找到终点或者所有的节点都被访问。

算法流程

步骤如下：

1. 初始化：将起点的距离设为0，其他节点的距离设为无穷大。将所有节点加入集合S中。
2. 找到S中距离起点最近的节点u，将其加入已访问的节点集合V中。
3. 对于所有与节点u相邻的节点v，更新其到起点的距离，如果有更短的路径，更新其距离。
4. 重复步骤2和步骤3，直到所有的节点都被访问过。

示例代码

#include <iostream>
#include <climits>
using namespace std;

const int MAXN = 100005;//可以根据题目要求修改
int d[MAXN];
bool used[MAXN];
int V, E;//V表示节点个数，E表示边的个数

struct edge {
    int to;
    int cost;
};

edge G[MAXN][MAXN];//邻接矩阵存图

void dijkstra(int s) {
    // 初始化
    for (int i = 1; i <= V; i++) {
        d[i] = INT_MAX;//将除了起点之外的节点距离都设置为无穷大
        used[i] = false;
    }
    d[s] = 0;

    while (true) {
        int v = -1;
        for (int u = 1; u <= V; u++) {
            if (!used[u] && (v == -1 || d[u] < d[v])) {
                v = u;
            }
        }
        if (v == -1) {
            break;
        }
        used[v] = true;

        // 更新所有与节点v相邻的节点的距离
        for (int u = 1; u <= V; u++) {
            if (G[v][u].cost != INT_MAX) {//如果u和v之间有边相连
                d[u] = min(d[u], d[v] + G[v][u].cost);//判断是否需要更新距离
            }
        }
    }
}

示例说明

例子1

给定起点S，终点T，求S到T的最短路径。

图中的数字表示边的权值。

      (4)
   S ------ T
  / \      / \
(2) (3) (2) (5)
 /     \  /   \
A        B      C

使用邻接矩阵存图的方式，在程序中输入该图的边的信息，然后使用Dijkstra算法求S到T的最短路径。

int main() {
    V = 4;
    E = 5;

    // 初始化邻接矩阵
    for (int i = 1; i <= V; i++) {
        for (int j = 1; j <= V; j++) {
            G[i][j].cost = INT_MAX;
        }
    }
    G[1][2].cost = 2;
    G[1][3].cost = 3;
    G[2][3].cost = 2;
    G[2][4].cost = 5;
    G[3][4].cost = 4;
    G[2][1].cost = 2;
    G[3][1].cost = 3;
    G[3][2].cost = 2;
    G[4][2].cost = 5;
    G[4][3].cost = 4;

    // 求最短路径
    dijkstra(1);

    // 输出结果：输出所有节点到起点的最短路径
    for (int i = 1; i <= V; i++) {
        cout << "distance from S to " << i << ": " << d[i] << endl;
    }

    return 0;
}

输出结果：

distance from S to 1: 0
distance from S to 2: 2
distance from S to 3: 3
distance from S to 4: 7

例子2

实际应用经常涉及到多个起点或终点的情况，求出这些点到其他节点的最短路径。

例如，从下面的图中的点1、2和7，分别到其他节点的最短路径。

                      (2)
                    /      \
               (4)/           \ (3)
                /               \
               1-------(6)--------2
                \               /
               (5)\           /(4)
                    \      /
                      (1)
                        7

多源最短路径问题可以把每个起点作为开始运行Dijkstra算法，最终获得每个点到起点的最短路径。这种方法叫做 Floyd 算法，时间复杂度较高，但对于较小的图来说是可行的。

// 计算多源最短路径
void floyd() {
    for (int k = 1; k <= V; k++) {
        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                G[i][j].cost = min(G[i][j].cost, G[i][k].cost + G[k][j].cost);
            }
        }
    }
}

int main() {
    V = 7;
    E = 10;

    // 初始化邻接矩阵
    for (int i = 1; i <= V; i++) {
        for (int j = 1; j <= V; j++) {
            if (i == j) {
                G[i][j].cost = 0;
            } else {
                G[i][j].cost = INT_MAX;
            }
        }
    }
    G[1][2].cost = 6;
    G[1][7].cost = 1;
    G[2][1].cost = 6;
    G[2][3].cost = 5;
    G[2][7].cost = 2;
    G[3][2].cost = 5;
    G[3][4].cost = 5;
    G[4][3].cost = 5;
    G[4][5].cost = 4;
    G[5][4].cost = 4;
    G[5][6].cost = 3;
    G[6][5].cost = 3;
    G[6][7].cost = 9;
    G[7][1].cost = 1;
    G[7][2].cost = 2;
    G[7][6].cost = 9;

    // 求多源最短路径
    floyd();

    // 输出结果：输出从点1、2、7到其他节点的最短路径
    cout << "distance from 1 to:" << endl;
    for (int i = 1; i <= V; i++) {
        cout << i << ": " << G[1][i].cost << endl;
    }
    cout << "distance from 2 to:" << endl;
    for (int i = 1; i <= V; i++) {
        cout << i << ": " << G[2][i].cost << endl;
    }
    cout << "distance from 7 to:" << endl;
    for (int i = 1; i <= V; i++) {
        cout << i << ": " << G[7][i].cost << endl;
    }

    return 0;
}

输出结果：

distance from 1 to:
1: 0
2: 6
3: 11
4: 16
5: 20
6: 23
7: 1
distance from 2 to:
1: 6
2: 0
3: 5
4: 10
5: 14
6: 17
7: 2
distance from 7 to:
1: 1
2: 2
3: 7
4: 12
5: 16
6: 9
7: 0

总结

Dijkstra算法可以求单源最短路径问题，时间复杂度为O(N^2)，当边很多时会很慢。若边很多（如>10^6，即100W），则可以使用堆优化版的Dijkstra算法，时间复杂度降为O(ElogV)。