Dijkstra

Dijkstra

Dijkstra算法用于解决单源最短路问题，假设起始点为S，在最开始我们可以知道S到某些点的距离，从中取出最小的一个，我们可以保证在我们取出这个最小值的时候不可能有任何路径可以更短的到达此点，，此过程使用了贪心的思想。每当我们找出一个这样的点就更新S到与此点相连的其它点的距离，我们每一次取点都保证取出的是最短的且未被访问的点，这就是Dijkstra算法。