狄克斯特拉算法

概述

1. 狄克斯特拉算法（Dijkstra's Algorithm）是一种用于计算单源最短路径的算法，适用于非负权重的有向图和无向图
   1. 对于狄克斯特拉算法而言，图必须有权重才行
   2. 如果图是无权图（即所有边的权重都相同，可以视为权重为 1）
      可以使用广度优先搜索（BFS）来找到最短路径
      因为 BFS 会按层次遍历图，首先访问到的节点一定是最短路径
2. 非负权重：
   1. 图中的所有边的权重（或成本）都必须是非负的，即权重不能是负数
   2. 狄克斯特拉算法无法处理负权重的边，因为负权重可能导致算法进入无限循环，从而无法正确计算最短路径
   3. 权重表示从一个节点到另一个节点的成本或距离
3. 有向图：
   1. 图中的边有方向性，即从一个节点指向另一个节点
   2. 例如，从节点 A 到节点 B 有一条边，但这条边并不意味着从 B 到 A 也有一条边
4. 无向图：
   1. 图中的边没有方向性，即边连接的两个节点之间可以相互到达
   2. 例如，从节点 A 到节点 B 有一条边，这意味着从 B 到 A 也有一条边，权重相同

主要思想

1. 狄克斯特拉算法的主要思想是通过贪心策略逐步找到从起点到各个节点的最短路径
2. 在每一步中，它选择当前距离最短的节点，然后更新其邻居节点的最短路径

步骤

1. 初始化
   1. 设置起点到自己的距离为 0，其他节点到起点的距离为无穷大
   2. 使用一个优先队列（或最小堆）来存储节点及其当前已知的最短距离
   3. 将起点放入优先队列
2. 迭代
   1. 从优先队列中取出距离最小的节点，记为当前节点
   2. 对于当前节点的每个邻居节点，计算从起点到该邻居节点的距离，如果该距离小于已知的最短距离，则更新该邻居节点的最短距离，并将其放入优先队列
   3. 重复上述过程，直到优先队列为空

场景

1. 路径规划：
   1. 如地图导航中计算最短路径
2. 网络路由：
   1. 在计算机网络中寻找从一个节点到另一个节点的最短路径
3. 资源分配：
   1. 在任务调度中寻找最优资源分配路径

示例有权图

有权有向图

1. 从节点 A 开始，计算到所有其他节点的最短路径
2. 初始化：distance[A] = 0, distance[B] = ∞, distance[C] = ∞, distance[D] = ∞, distance[E] = ∞
3. 将 A 放入优先队列
4. 取出 A，更新其邻居：
   1. B：distance[B] = 0 + 1 = 1
   2. C：distance[C] = 0 + 2 = 2
   3. D：distance[D] = 0 + 4 = 4
5. 取出 B，更新其邻居：
   1. E：distance[E] = 1 + 2 = 3
6. 取出 C，更新其邻居：
   1. <code>E：distance[E] = 2 + 1 = 3（已经是最短距离，不更新）
7. 取出 E，更新其邻居：
   1. D：distance[D] = 3 + 3 = 6（已经是最短距离，不更新）
8. 取出 D，没有需要更新的邻居
9. 最终最短路径为：A -> B = 1, A -> C = 2, A -> D = 4, A -> E = 3

有向图邻接表表示

1. 假设有一个图，表示为邻接表：

2. 邻接表表示为：

3. 解释：
   1. 把ABCD分别标记为0123
   2. graph容器中，下标为0的项，用来存A相关的数据
   3. 比如{1,1}表示，0与1之间的权重是1，即A和B之间的权重是1
   4. {2,2}表示，0与2之间的权重是2，即A和C之间的权重是2

有权无向图和邻接表

1. 图

2. 邻接表表示为：

示例代码

1. 图

2. 以下是一个使用优先队列（最小堆）实现