Dijkstra算法举例分析
什么是Dijkstra算法?
Dijkstra算法是一种用于求解带权重图中最短路径的算法,由荷兰的计算机科学家Edsger W. Dijkstra在1959年提出。该算法适用于有向或无向图,但要求图中的边的权重必须为非负值。
该算法的基本思想是从起点开始,逐步确定到其他顶点的最短路径。在执行过程中,通过维护一个距离向量来记录到达各个顶点的最短路径长度,同时再维护一个集合来记录已经确定了最短路径的顶点。在每一次迭代中,选择距离向量中未确定最短路径的顶点中距离最小的顶点,更新距离向量和已确定最短路径的集合,并重复这个过程直到所有顶点都被确定了最短路径。
算法步骤
1. 初始化:设起点为源点,将源点到自己的距离设为0,将源点到其他顶点的距离初始化为无穷大。
distance[source] = 0
distance[others] = infinity
2. 选取距离向量中距离最小的顶点作为当前顶点。
min_distance = min(distance)
current_vertex = min_distance_vertex
3. 对于当前顶点的所有邻居顶点,计算经过当前顶点到达邻居顶点的距离,并更新距离向量。
for neighbour in neighbours(current_vertex):
new_distance = distance[current_vertex] + weight(current_vertex, neighbour)
if new_distance < distance[neighbour]:
distance[neighbour] = new_distance
4. 标记当前顶点为已确定最短路径的顶点。
marked_vertices.add(current_vertex)
5. 重复步骤2到4,直到所有顶点都被标记为已确定最短路径的顶点。
算法示例
假设有以下带权重的无向图:
1 - 2 - 4
/ \ / \
0---3---5
起点为顶点0,我们使用Dijkstra算法来找到从起点到其他顶点的最短路径。
1. 初始化:
distance[0] = 0
distance[1-5] = infinity
2. 选取起点0作为当前顶点。
min_distance = 0
current_vertex = 0
3. 计算经过当前顶点到达其他顶点的距离,并更新距离向量:
distance[0-3] = [0, 6, 1, 2, infinity, infinity]
4. 将顶点0标记为已确定最短路径的顶点。
marked_vertices = {0}
5. 重复步骤2到4,依次选取经过顶点3和顶点1的最小距离顶点并更新距离向量,直到所有顶点都被标记为已确定最短路径的顶点。
最后得到的距离向量为:
distance = [0, 5, 1, 2, 6, 7]
可见,从顶点0到其他顶点的最短路径分别为:
0 - 2 - 4(距离为5)
0 - 3(距离为1)
0 - 3 - 5(距离为2)
猜您想看
-
LeetCode中如何不用加减乘除做加法
背景介绍Lee...
2023年07月21日 -
PHP中的图片压缩和优化技巧
图片压缩和优化...
2023年05月05日 -
博客快速整合公众号导流工具Hexo的用法
Hexo是一个...
2023年07月23日 -
crontab任务自动化设置
1. 什么是c...
2024年05月30日 -
Solidity地址类型有哪些
Solidit...
2023年07月23日 -
为什么我和我的朋友不能通过局域网进行文件共享?
如何在局域网中...
2023年05月03日