贪心算法单源最短路径

‘壹’ 直观理解：单源点最短路径——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算法的计算过程的简单描述。