Dijkstra算法解析

Dijkstra算法，用于求解图中从一个起点到其他所有节点的最短路径。解决单源最短路径问题的有效方法。

条件

有向

带权路径

时间复杂度 O（n平方）

方法步骤

1 把图上的点分为两个集合 要求的起点 和除了起点之外的点 。能直达的写上权值 不能直达的写上无穷 自己到自己的距离是0

2 在除起点以外的中找权值最小的顶点，这个顶点加入起点所在的集合。由于新顶点的并入，可以把新顶点作为中转点，再重新计算起点到所有除已经并入顶点的距离，找最小的继续并入，直到所有顶点并入起点所在的集合。

以下是对代码的详细解析和注释：

代码解析

全局变量定义

#define N 1005 // 定义最大顶点数为1005
int n, m; // n表示顶点数，m表示边数
bool str[N]; // 用于标记是否已确定最短路径
int dis[N]; // 存储从起始点到各个顶点的最短距离
int g[N][N]; // 邻接矩阵，存储图的结构

• N：定义图中最大顶点数为1005。

• n 和 m：分别表示图中的顶点数和边数。

• str：布尔数组，用于标记某个顶点是否已经确定了最短路径。

• dis：数组，存储从起点到每个顶点的最短距离。

• g：邻接矩阵，g[i][j] 表示从顶点 i 到顶点 j 的距离。

Dijkstra算法实现

void dijkstra() {// 初始化dis数组为一个很大的值（这里选择0x3f3f3f3f）memset(dis, 0x3f3f3f3f, sizeof(dis));// 起始点到自身的距离为0dis[1] = 0;for (int i = 1; i <= n; ++i) {int temp = -1; // 选择未确定的顶点// 寻找当前未确定的最小距离顶点for (int j = 1; j <= n; ++j)if (!str[j] && (temp == -1 || dis[j] < dis[temp]))temp = j;// 更新与该顶点相邻的其他顶点的距离for (int j = 1; j <= n; ++j)dis[j] = min(dis[j], dis[temp] + g[temp][j]);// 标记该顶点已经确定了最短路径str[temp] = true;}// 输出结果for (int i = 1; i <= n; ++i) {if (dis[i] == 0x3f3f3f3f)cout << "-1" << " "; // 如果没有到该顶点的路径则输出-1elsecout << dis[i] << " "; // 否则输出最短距离}
}

1. 初始化：

   • memset(dis, 0x3f3f3f3f, sizeof(dis));：将 dis 数组初始化为一个很大的值（0x3f3f3f3f），表示初始时从起点到其他顶点的距离是无穷大。

   • dis[1] = 0;：将起点到自身的距离设置为0。

2. 主循环：

   • for (int i = 1; i <= n; ++i)：循环 n 次，每次找到一个未确定最短路径的顶点。

   • int temp = -1;：初始化当前未确定的最短距离顶点为 -1。

   • for (int j = 1; j <= n; ++j)：遍历所有顶点，找到未确定最短路径的顶点中距离最短的顶点 temp。

     • if (!str[j] && (temp == -1 || dis[j] < dis[temp]))：如果顶点 j 未确定最短路径且距离更短，则更新 temp。

   • for (int j = 1; j <= n; ++j)：更新与顶点 temp 相邻的其他顶点的距离。

     • dis[j] = min(dis[j], dis[temp] + g[temp][j]);：如果通过 temp 到达 j 的距离更短，则更新 dis[j]。

   • str[temp] = true;：标记顶点 temp 已经确定了最短路径。

3. 结果输出：

   • 遍历 dis 数组，输出从起点到每个顶点的最短距离。

   • 如果 dis[i] 仍然是 0x3f3f3f3f，表示没有路径到达顶点 i，输出 -1。

   • 否则输出 dis[i]。

主函数

int main() {// 初始化邻接矩阵g为一个很大的值memset(g, 0x3f3f3f3f, sizeof(g));// 输入顶点数n和边数mcin >> n >> m;while (m--) { // 处理每一条边的输入int x, y, z;cin >> x >> y >> z;// 更新邻接矩阵g中的权值g[x][y] = min(g[x][y], z);}// 调用dijkstra函数求解dijkstra();return 0;
}

1. 初始化邻接矩阵：

   • memset(g, 0x3f3f3f3f, sizeof(g));：将邻接矩阵 g 初始化为一个很大的值（0x3f3f3f3f），表示初始时图中没有边。

2. 输入图的边：

   • cin >> n >> m;：读取顶点数 n 和边数 m。

   • while (m--)：循环 m 次，读取每一条边的信息。

     • cin >> x >> y >> z;：读取边的起点 x、终点 y 和权重 z。

     • g[x][y] = min(g[x][y], z);：更新邻接矩阵 g 中的权值，如果有多条边连接同一对顶点，只保留权重最小的那条边。

3. 调用Dijkstra算法：

   • dijkstra();：调用 dijkstra 函数求解最短路径。

4. 输出结果：

   • dijkstra 函数会输出从起点到每个顶点的最短距离。

示例输入和输出

示例输入

5 7
1 2 4
1 3 3
2 4 2
3 2 1
3 4 5
4 5 1
2 5 7

示例输出

0 2 3 4 5

解释

• 顶点 1 到顶点 2 的最短距离为 2（1 -> 3 -> 2）。

• 顶点 1 到顶点 3 的最短距离为 3（1 -> 3）。

• 顶点 1 到顶点 4 的最短距离为 4（1 -> 3 -> 2 -> 4）。

• 顶点 1 到顶点 5 的最短距离为 5（1 -> 3 -> 2 -> 4 -> 5）。

关键点总结

1. 邻接矩阵：使用二维数组 g[N][N] 表示图的结构，g[i][j] 表示从顶点 i 到顶点 j 的距离。

2. 选择最短距离顶点：通过遍历所有顶点，找到未确定最短路径的顶点中距离最短的顶点。

3. 更新邻接顶点的距离：通过当前顶点更新其邻接顶点的距离。

4. 标记顶点：使用布尔数组 str 标记顶点是否已经确定了最短路径。

Dijkstra算法详细步骤解析

1. 初始化

在算法开始之前，需要进行以下初始化操作：

1. 初始化距离数组 dis：

   • 将 dis 数组中的所有元素初始化为一个很大的值（如 0x3f3f3f3f），表示从起点到其他顶点的距离初始为无穷大。

   • 将起点的距离设置为 0，即 dis[start] = 0。

2. 初始化访问标记数组 str：

   • 将 str 数组中的所有元素初始化为 false，表示所有顶点初始时都未被访问过。

3. 初始化邻接矩阵 g：

   • 将邻接矩阵 g 中的所有元素初始化为一个很大的值（如 0x3f3f3f3f），表示初始时图中没有边。

2. 主循环

Dijkstra算法的核心是一个主循环，该循环执行 n 次（n 为顶点数），每次找到一个未访问的最短距离顶点，并更新其邻接顶点的距离。

1. 选择未访问的最短距离顶点：

   • 遍历所有顶点，找到未访问的顶点中距离最短的顶点 u。

   • 如果所有顶点都已被访问过，或者没有找到未访问的顶点，则退出循环。

2. 更新邻接顶点的距离：

   • 遍历顶点 u 的所有邻接顶点 v，如果通过 u 到达 v 的距离更短，则更新 dis[v]。

   • 具体来说，如果 dis[u] + g[u][v] < dis[v]，则更新 dis[v] = dis[u] + g[u][v]。

3. 标记顶点为已访问：

   • 将顶点 u 标记为已访问，即 str[u] = true，避免重复处理。

3. 结果输出

在主循环结束后，dis 数组中存储了从起点到每个顶点的最短距离。遍历 dis 数组，输出结果：

• 如果 dis[i] 仍然是初始的大值（如 0x3f3f3f3f），表示没有路径到达顶点 i，输出 -1。

• 否则，输出 dis[i]，表示从起点到顶点 i 的最短距离。

示例执行过程

假设图的结构如下：

• 顶点数 n = 5

• 边数 m = 7

• 边的权重如下：

  • 1 -> 2: 4

  • 1 -> 3: 3

  • 2 -> 4: 2

  • 3 -> 2: 1

  • 3 -> 4: 5

  • 4 -> 5: 1

  • 2 -> 5: 7

初始化

• dis 数组：[0, 0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f]

• str 数组：[false, false, false, false, false]

• g 邻接矩阵：

  [[0x3f3f3f3f, 4, 3, 0x3f3f3f3f, 0x3f3f3f3f],[0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f, 2, 0x3f3f3f3f],[0x3f3f3f3f, 1, 0x3f3f3f3f, 5, 0x3f3f3f3f],[0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f, 1],[0x3f3f3f3f, 7, 0x3f3f3f3f, 0x3f3f3f3f, 0x3f3f3f3f]
  ]

第1次循环

1. 选择未访问的最短距离顶点：

   • 遍历所有顶点，找到未访问的顶点中距离最短的顶点 u = 1（起点）。

2. 更新邻接顶点的距离：

   • 遍历顶点 1 的邻接顶点 2 和 3：

     • dis[2] = min(dis[2], dis[1] + g[1][2]) = min(0x3f3f3f3f, 0 + 4) = 4

     • dis[3] = min(dis[3], dis[1] + g[1][3]) = min(0x3f3f3f3f, 0 + 3) = 3

3. 标记顶点为已访问：

   • str[1] = true

第2次循环

1. 选择未访问的最短距离顶点：

   • 遍历所有顶点，找到未访问的顶点中距离最短的顶点 u = 3（dis[3] = 3）。

2. 更新邻接顶点的距离：

   • 遍历顶点 3 的邻接顶点 2 和 4：

     • dis[2] = min(dis[2], dis[3] + g[3][2]) = min(4, 3 + 1) = 4

     • dis[4] = min(dis[4], dis[3] + g[3][4]) = min(0x3f3f3f3f, 3 + 5) = 8

3. 标记顶点为已访问：

   • str[3] = true

第3次循环

1. 选择未访问的最短距离顶点：

   • 遍历所有顶点，找到未访问的顶点中距离最短的顶点 u = 2（dis[2] = 4）。

2. 更新邻接顶点的距离：

   • 遍历顶点 2 的邻接顶点 4 和 5：

     • dis[4] = min(dis[4], dis[2] + g[2][4]) = min(8, 4 + 2) = 6

     • dis[5] = min(dis[5], dis[2] + g[2][5]) = min(0x3f3f3f3f, 4 + 7) = 11

3. 标记顶点为已访问：

   • str[2] = true

第4次循环

1. 选择未访问的最短距离顶点：

   • 遍历所有顶点，找到未访问的顶点中距离最短的顶点 u = 4（dis[4] = 6）。

2. 更新邻接顶点的距离：

   • 遍历顶点 4 的邻接顶点 5：

     • dis[5] = min(dis[5], dis[4] + g[4][5]) = min(11, 6 + 1) = 7

3. 标记顶点为已访问：

   • str[4] = true

第5次循环

1. 选择未访问的最短距离顶点：

   • 遍历所有顶点，找到未访问的顶点中距离最短的顶点 u = 5（dis[5] = 7）。

2. 更新邻接顶点的距离：

   • 顶点 5 没有邻接顶点，无需更新。

3. 标记顶点为已访问：

   • str[5] = true

结果输出

遍历 dis 数组，输出从起点到每个顶点的最短距离：

• dis[1] = 0

• dis[2] = 4

• dis[3] = 3

• dis[4] = 6

• dis[5] = 7

关键点总结

1. 选择未访问的最短距离顶点：

   • 每次选择未访问的顶点中距离最短的顶点，确保每一步都选择当前最优的顶点进行处理。

2. 更新邻接顶点的距离：

   • 通过当前顶点更新其邻接顶点的距离，确保每一步都更新到最新的最短距离。

3. 标记顶点为已访问：

   • 避免重复处理已访问的顶点，提高算法的效率。

4. 结果输出：

   • 最终输出从起点到每个顶点的最短距离，如果没有路径到达某个顶点，则输出 -1