4.4 Dijkstra算法

4.4.1 数据结构-优先队列

1. 优先队列中的每个元素都有相对应的优先级。

2. 在进行移除元素操作时，高优先级的元素将优先被移除。

3. 如果两个元素的优先级相同，则按照先进先出（FIFO）的原则进行排序。

4.4.2 基本思想

1. 初始化：
1. 创建一个数组g[]，其中g[i]表示从源节点start到节点i的最小cost，初始时，源节点的cost为0。
2. 创建一个布尔数组 visited[] 来跟踪每个节点是否已被访问过，初始时，所有顶点都未访问
3. 创建一个优先队列open_list，用于根据cost选择下一个要处理的节点。优先队列中的每个元素是一个包含顶点和cost的配对，初始时将源节点start和其cost(0)加入优先队列。

2. 循环处理优先队列中的节点：
1. 从优先队列中取出cost最小的节点v ，并将节点v 标记为已访问，若节点v就是目标节点，则提前返回。
2. 遍历节点v 中所有未被访问过的邻接节点，对于每一个邻接节点next ：
1. 计算邻接节点next 的cost。
2. 若邻接节点next 不在优先队列中，则将邻接节点next 和其对应的cost加入优先队列，并在数组g[] 中设置邻接节点next 的cost，最后将临接节点next 的父节点设为v 。
3. 若邻接节点next 在优先队列中，则在数组g[]和优先队列open_list中更新节点next 的相关信息，最后将临接节点next 的父节点设为v 。
3. 继续处理优先队列中的顶点，直到队列为空或所有顶点都被访问。

3. 从目标节点goal开始，通过父节点向回追溯，直到起始节点，最终得到一条路径。

4.4.3 Dijkstra算法的图解

• 源节点到自身的cost为0。

• 源节点到其它节点的cost还没有确定，暂时先标记为无穷大。

1. 从源节点0 开始，将其加入到已访问列表中，并从未访问列表中删除。同时在未访问列表中更新源节点0 的邻近节点（节点1和节点2）的信息。
1. 节点1 ：节点1 最短路径为0 —> 1 ，cost为2，父节点为0 。
2. 节点2：节点2 最短路径为0 —> 2 ，cost为6，父节点为0 。

2. 查看未访问列表，节点1 的cost最小，因此将其加入到已访问列表中，并从未访问列表中删除。同时在未访问列表中更新节点1 的邻近节点（节点3）的信息。
1. 节点3：节点3的最短路径为0 —> 1 —> 3 ，cost为7，父节点为1。

3. 查看未访问列表，节点2 的cost最小，因此将其加入到已访问列表中，并从未访问列表中删除。同时在未访问列表中更新节点2 的邻近节点（节点3）的信息。
1. 节点3：此时，节点3 有两条可选路径：0 —> 1 —> 3 和0 —> 2 —> 3 ，前者的cost是7，后者的cost是14，因此选择前者，即节点3的最短路径为0 —> 1 —> 3 ，cost为7，父节点为1 。

4. 查看未访问列表，节点3 的cost最小，因此将其加入到已访问列表中，并从未访问列表中删除。同时在未访问列表中更新节点3 的邻近节点（节点4和节点5）的信息。
1. 节点4：节点4的最短路径为0 —> 1 —> 3 —> 4 ，cost为17，父节点为3 。
2. 节点5：节点5的最短路径为0 —> 1 —> 3 —> 5 ，cost为22，父节点为3 。

5. 查看未访问列表，节点4 的cost最小，因此将其加入到已访问列表中，并从未访问列表中删除。同时在未访问列表中更新节点4 的邻近节点（节点5和节点6）的信息。
1. 节点5：此时节点5 有两条可选路径：0 —> 1 —> 3 —> 5 和0 —> 1 —> 3 —> 4 —> 5 ，前者的cost是22，后者的cost是23，因此选择前者，即节点5 的最短路径为0 —> 1 —> 3 —> 5 ，父节点为3 。
2. 节点6 ：节点6 的最短路径为0 —> 1 —> 3 —> 4 —> 6 ，cost为19，父节点为4 。

6. 查看未访问列表，节点6 的cost最小，因此将其加入到已访问列表中，并从未访问列表中删除。同时在未访问列表中更新节点6 的邻近节点（节点5）的信息。
1. 节点5：此时节点5共有3条可选路径（如下），因此最短路径为0 —> 1 —> 3 —> 5 ，cost为22，父节点为3。
1. 0 —> 1 —> 3 —> 5 ，cost为22。
2. 0 —> 1 —> 3 —> 4 —> 5 ，cost为23。
3. 0 —> 1 —> 3 —> 4 —> 6 —> 5 ,cost为25。

7. 查看未访问列表，节点5 的cost最小，因此将其加入到已访问列表中，并从未访问列表中删除。此时未访问列表中没有节点，因此搜索结束。此时，我们可以给定目标节点，并通过回溯父节点的方式找到从源节点到目标节点的最短路径。例如我们另节点6 是目标节点，可以得到从源节点到目标节点的最短路径为：0 —> 1 —> 3 —> 4 —> 6

4.4.4 Dijkstra算法特点

• 优点：
（1）总能找到从单个源点到图中所有其他顶点的最短路径，前提是所有的边权重都是非负的。
（2）原理简单，应用广泛，且满足最优性原则。

• 缺点：
（1）搜索时没有引入目标节点的信息，导致搜索效率较低。
（2）不适用于包含负权重的图。

4.4.5 参考