Dijkstra/迪杰斯特拉算法
迪杰斯特拉算法（Dijkstra's Algorithm）是一种用于寻找图中从一个起点到其他所有顶点的最短路径的算法。它是一个贪心算法，通过每次选择当前最短路径的节点来逐步扩展解决方案。
假设我们有一个加权无向图，节点代表顶点，边的权重代表连接两个顶点的距离。下面我们将通过一个具体例子手动计算迪杰斯特拉算法的步骤和思路。
例子：
考虑节点 A, B, C, D, E, F无向图
边的权重（数字表示）：
- A ↔ B 权重为 1
- A ↔ D 权重为 7
- B ↔ C 权重为 4
- B ↔ E 权重为 3
- C ↔ F 权重为 3
- D ↔ E 权重为 1
- E ↔ F 权重为 2
起始节点为 A，我们要找从 A 到所有其他节点的最短路径。
迪杰斯特拉算法手动计算步骤
步骤 1: 初始化
- 初始化每个节点到起点的距离，除了起点自己，其它所有节点的距离为无穷大。
- 标记所有节点为未访问。
- 设定起点 A 到 A 的距离为 0。
| 节点 | 距离 | 前驱节点 | 访问状态 |
|---|---|---|---|
| A | 0 | - | 未访问 |
| B | ∞ | - | 未访问 |
| C | ∞ | - | 未访问 |
| D | ∞ | - | 未访问 |
| E | ∞ | - | 未访问 |
| F | ∞ | - | 未访问 |
步骤 2: 选择当前未访问节点中距离起点最A进行访问并标记访问
当前起点 A，距离为 0。访问邻接节点并更新它们的距离。
- A → B 的距离是 1，更新 B 的距离为 1。
- A → D 的距离是 7，更新 D 的距离为 7。
| 节点 | 距离 | 前驱节点 | 访问状态 |
|---|---|---|---|
| A | 0 | - | 已访问 |
| B | 1 | A | 未访问 |
| C | ∞ | - | 未访问 |
| D | 7 | A | 未访问 |
| E | ∞ | - | 未访问 |
| F | ∞ | - | 未访问 |
步骤 3: 选择距离起点最近的未访问节点 B
当前未访问节点中距离起点最近的是 B，距离为 1。访问邻接节点并更新它们的距离。
- B → C 的距离是 4，总距离是 1 + 4 = 5，更新 C 的距离为 5。
- B → E 的距离是 3，总距离是 1 + 3 = 4，更新 E 的距离为 4。
| 节点 | 距离 | 前驱节点 | 访问状态 |
|---|---|---|---|
| A | 0 | - | 已访问 |
| B | 1 | A | 已访问 |
| C | 5 | B | 未访问 |
| D | 7 | A | 未访问 |
| E | 4 | B | 未访问 |
| F | ∞ | - | 未访问 |
步骤 4: 选择距离起点最近的未访问节点 E
当前未访问节点中距离起点最近的是 E，距离为 4。访问邻接节点并更新它们的距离。
- E → F 的距离是 2，总距离是 4 + 2 = 6，更新 F 的距离为 6。
- E → D 的距离是 1，总距离是 4 + 1 = 5，更新 D 的距离为 5。
| 节点 | 距离 | 前驱节点 | 访问状态 |
|---|---|---|---|
| A | 0 | - | 已访问 |
| B | 1 | A | 已访问 |
| C | 5 | B | 未访问 |
| D | 5 | E | 未访问 |
| E | 4 | B | 已访问 |
| F | 6 | E | 未访问 |
步骤 5: 选择距离起点最近的未访问节点 D
当前未访问节点中距离起点最近的是 D，距离为 5。访问邻接节点并更新它们的距离。
- D → E 的距离是 1，总距离是 5 + 1 = 6，但 E 的当前距离是 4，因此不更新 E。
- D → F 的距离是 ∞，因此不会更新 F。
| 节点 | 距离 | 前驱节点 | 访问状态 |
|---|---|---|---|
| A | 0 | - | 已访问 |
| B | 1 | A | 已访问 |
| C | 5 | B | 未访问 |
| D | 5 | E | 已访问 |
| E | 4 | B | 已访问 |
| F | 6 | E | 未访问 |
步骤 6: 选择距离起点最近的未访问节点 C
当前未访问节点中距离起点最近的是 C，距离为 5。访问邻接节点并更新它们的距离。
- C → F 的距离是 3，总距离是 5 + 3 = 8，但 F 的当前距离是 6，因此不更新 F。
| 节点 | 距离 | 前驱节点 | 访问状态 |
|---|---|---|---|
| A | 0 | - | 已访问 |
| B | 1 | A | 已访问 |
| C | 5 | B | 已访问 |
| D | 5 | E | 已访问 |
| E | 4 | B | 已访问 |
| F | 6 | E | 未访问 |
步骤 7: 选择距离起点最近的未访问节点 F
最后，未访问节点中距离起点最近的是 F，距离为 6。
| 节点 | 距离 | 前驱节点 | 访问状态 |
|---|---|---|---|
| A | 0 | - | 已访问 |
| B | 1 | A | 已访问 |
| C | 5 | B | 已访问 |
| D | 5 | E | 已访问 |
| E | 4 | B | 已访问 |
| F | 6 | E | 已访问 |
最终结果
- A → B → E → F: 最短路径为 0 → 1 → 4 → 6。
- A → B → C: 最短路径为 0 → 1 → 5。
- A → D → E → F: 最短路径为 0 → 7 → 4 → 6。
总结：
- 迪杰斯特拉算法是一种贪心算法，每次选取当前未访问节点中距离起点最近的节点进行处理，并更新其邻接节点的最短距离。
- 在手动计算过程中，最重要的是不断更新节点的最短距离，并确保每次选择当前未访问节点中最短的一个进行处理，直到所有节点都被访问。
以下是c++代码实现:
#include <iostream>using namespace std;#define maxv 8typedef struct { char vexs[8]; // 顶点表 int edges[8][8]; // 邻接矩阵 int vnum, ednum; // 顶点数，边数} MGraph;const int no = 10000; void initG(MGraph &G){ // 顶点表：图的8个顶点分别是 A, B, C, D, E, F, G, H G.vexs[0] = 'A'; G.vexs[1] = 'B'; G.vexs[2] = 'C'; G.vexs[3] = 'D'; G.vexs[4] = 'E'; G.vexs[5] = 'F'; G.vexs[6] = 'G'; G.vexs[7] = 'H'; // 顶点数和边数 G.vnum = maxv; G.ednum = 14; // 假设图中有14条边 // 邻接矩阵初始化 // 设定 no表示无边，正数表示边的权重 int matrix[8][8] = { {no, 10, 3, 5, no, no, no, no}, // A -> B(10), A -> C(3), A -> D(5) {no, no, 2, no, 7, 4, no, no}, // B -> C(2), B -> E(7), B -> F(4) {no, no, no, no, 1, no, 8, no}, // C -> E(1), C -> G(8) {no, no, no, no, 6, 2, 9, no}, // D -> E(6), D -> F(2), D -> G(9) {no, no, no, no, no, no, no, 3}, // E -> H(3) {no, no, no, no, no, no, no, 6}, // F -> H(6) {no, no, no, no, no, no, no, 2}, // G -> H(2) {no, no, no, no, no, no, no, no} // H 没有出边 }; // 将邻接矩阵填入 G.edges 中 for (int i = 0; i < G.vnum; i++) { for (int j = 0; j < G.vnum; j++) { G.edges[i][j] = matrix[i][j]; } }} // 迪杰斯特拉算法void djstl(MGraph *G, int P[maxv], int D[maxv]) { bool final[maxv] = {false}; // 所有节点初始化为未确定最短路径 final[0] = true; // 源点加入最短路径集合 // 初始化 D 和 P 数组 for(int i = 0; i < G->vnum; i++) { D[i] = G->edges[0][i]; // 源点到其它节点的初始距离 P[i] = 0; // 前驱节点初始化为0 } D[0] = 0; // 源点到源点的距离为0 P[0] = -1; // 源点没有前驱 // 主循环 for (int i = 1; i < G->vnum; i++) { int j = 0; int min = no; // 最小路径初始化为无穷大 for (int k = 0; k < G->vnum; k++) { if (!final[k] && D[k] < min) { // 找到未确定的最短路径 j = k; min = D[k]; } } final[j] = true; // 将顶点j加入已确定集合 for (int k = 0; k < G->vnum; k++) { if (!final[k] && (D[j] + G->edges[j][k] < D[k])) { D[k] = D[j] + G->edges[j][k]; P[k] = j; // 更新前驱节点 } } } // 输出最短路径结果 for (int i = 1; i < G->vnum; i++) { cout << "最短路径到 " << G->vexs[i] << " : 路径长度 = " << D[i] << endl; int pre = P[i]; cout << G->vexs[i]; while (pre != -1) { cout << "<-" << G->vexs[pre]; pre = P[pre]; } cout << endl; }} void printG(MGraph G) { // 打印图的邻接矩阵 // 打印图的邻接矩阵 printf("图的邻接矩阵:\n"); printf(" \t"); for (int i = 0; i < G.vnum; i++) { printf(" \t%c ", G.vexs[i]); } printf("\n"); for (int i = 0; i < G.vnum; i++) { printf("\t%c", G.vexs[i]); for (int j = 0; j < G.vnum; j++) { if (G.edges[i][j] == no) { printf("\t. "); // 无边的地方用'.'表示 } else { printf("\t%2d ", G.edges[i][j]); } } printf("\n"); }} // int main() { // 创建图 MGraph G; initG(G); printG(G); int P[maxv]; int D[maxv]; djstl(&G, P, D); return 0;}
运行结果:
