直观理解:单源点最短路径——Dijkstra算法
Dijkstra算法是由荷兰计算机科学家 Edsger Wybe Dijkstra于1959年提出的单源点最短路径算法(SSSP:Single Souce Shortest Path)。是一个解决加权图(不含负权重的边)中从一个顶点到其余各个顶点最短路径问题的算法。Dijkstra算法是一个集 贪心算法 , 广度优先搜索(BFS) 和 动态规划 于一身的最短路径算法。Dijkstra算法的主要特点是从起源点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接顶点,直到扩展到终点为止。
Dijkstra算法通过维护两个集合: (已求出最短路径的顶点)和 (未求出最短路径的顶点),每次迭代地从 中移除路径距离最小的点到集合 中,并通过这个新移入的点来更新 中各个顶点到源点的最短路径,直到集合 为空。下面我们通过一个例子来简单描述Dijkstra算法的过程。
假设我们有如下的图,其中顶点A未此次算法的起点:
首先我们需要初始化两个集合 和 ,以及 中每个顶点到源点的距离,若不直接于A相邻,结果置为正无穷∞。
Step 1: 从集合 中挑选出距离最小的点,这里会挑选出顶点F,集合 和 变更为: , ,根据最新的 ,重新计算 中顶点到源点A的最短距离。
Step 2:: 从集合 中挑选出距离最小的点,这里会挑选出顶点E,集合 和 变更为: , ,根据最新的 ,重新计算 中顶点到源点A的最短距离。
Step 3: 从集合 中挑选出距离最小的点,这里会挑选出顶点C,集合 和 变更为: , ,根据最新的 ,重新计算 中顶点到源点A的最短距离。
Step 4: 从集合 中挑选出距离最小的点,这里会挑选出顶点D,集合 和 变更为: , ,根据最新的 ,重新计算 中顶点到源点A的最短距离。
Step 5: 从集合 中挑选出距离最小的点,这里会挑选出顶点B,集合 和 变更为: , ,根据最新的 ,重新计算 中顶点到源点A的最短距离。
Step 6: 从集合 中挑选出距离最小的点,这里会挑选出顶点G,集合 和 变更为: , ,由于集合 为空,算法停止迭代,输出结果。
以上就是对Dijkstra算法的计算过程的简单描述。