播放
速度:
0.5
1
2
5
算法概览
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。
算法示例7为源点,最终结果为源点7到各个节点的最短距离。 算法包含未确定最短距离节点列表和已确定最短节点列表,算法过程逐步将未确定距离节点的列表中的元素移动到已确定距离节点列表。 1.首先初始化源点到各个节点的距离。 2.再从未确定列表中找寻距离最短的节点。 3.更新源点距离其他未确定距离的节点。 4.重复步骤2和步骤3,直至所有节点处理完毕。