Dijkstra算法详解——求解单源最短路径问题

Dijkstra算法是一种经典的图论算法，用于解决从单个源点到其他所有顶点的最短路径问题。以下是该算法的具体步骤和实现细节：

如图所示，假设我们需要找到从点1到其他所有顶点的最短路径。

算法思路：

1. 首先，找到距离源点1最近的顶点k（这里的距离是指图中的权重，不一定是直线距离）。可以确定此时k点已经找到了最短路径。将k点加入集合S。
2. 当k点被加入集合S后，源点1到其他顶点的最短距离可能会发生变化，因此需要更新这些顶点的最短距离信息。
3. 重复上述步骤，每次选择一个顶点加入集合S，直到所有顶点都被处理完毕。

所需数据结构：

• 图G，通常使用邻接矩阵表示。
• 最短路径表D[n]，用于记录从源点到每个顶点的最短距离。
• 集合final[n]，用于标记顶点是否已加入集合S。

代码实现：

#include 
using namespace std;
#define INFINITY 2147483647

// 无向图的表示
class Graph {
public:
    int vexnum;
    int** Arcs;
};

// 集合final和集合D
bool final[10010];
int D[10010];

// 初始化工作
void Init(Graph &MyGraph, int n) {
    // 为图动态分配内存
    MyGraph.Arcs = new int*[n + 1];
    for (int i = 0; i <= n; i++) {
        MyGraph.Arcs[i] = new int[n + 1];
    }

    // 将所有的边都初始化为无穷大，并将所有点都排除到集合S外
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            MyGraph.Arcs[i][j] = INFINITY;
        }
        final[i] = false;
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    Graph MyGraph;
    Init(MyGraph, n);
    MyGraph.vexnum = n;

    // 录入边的信息
    int a, b;
    for (int i = 0; i > a >> b;
        cin >> MyGraph.Arcs[a][b];
        MyGraph.Arcs[b][a] = MyGraph.Arcs[a][b];
    }

    // 用图G初始化D表，并将源点加入S
    D[1] = 0;
    final[1] = true;
    for (int i = 2; i <= n; i++) {
        D[i] = MyGraph.Arcs[1][i];
    }

    // 每次找到距离源点最近的点并入S，一共有vexnum-1个点需要处理
    for (int i = 0; i