如何写Dijkistra与A*算法
Dijkistra’s
我们需要维护两个set：
- Set A: Vertices that are included in the shortest-path tree.
- Set B: Vertices that are not yet included in the shortest-path tree.
At every step of the algorithm, 我们从set B中取走一个vertice，放到set A里。 至于取走哪个vertice, 我们将set B里的vertices进行了排序，priority就是谁离start node距离最短，就先谁。
所以最开始set A是空的，而set B是包含了所有的vertices，但是我们还不知道每个vertice到底离source node多远，于是我们就默认设置为无穷大。由于source node与自己的距离为0，所以最先从set B中取出，放到set A里。我们找到source node的adjacent nodes，由于我们知道它与它的adjacent nodes的距离，于是我们就可以将这几个nodes的（离source node多远）信息进行update，从无穷大更新到真实的。于是我们就可以从刚刚更新的几个source node的adjacent nodes中取个最小的，进行新一轮的计算。即找到最新取出的这个node U的adjacent nodes, 然后对于将U的邻近node，我们计算一下node U到source node的距离+node U到它的每个邻近node的距离，看是不是比之前的已经保存的值小，小的话就更新，不然就不更新。然后在取出新的。以此类推，知道set B为空，set A包含了所有的vertices。例子就可以从Dijkstra’s shortest path algorithm | Greedy Algo-7中看到。
A*
同样，我们也需要维护两个set：