Dijkstra 算法

all the nodes should be carectorized into three groups: (visited, front, unknown) we should pay special attention to front group.

The Dijkstra Algorithm:

front = start node

while front is not empty:

　　get node n with minimum cost in the front group, and mark it as visited

　　for any direct neighbour m of n, and not in the visited group:

　　　　add it to front group if it is not in the front group

　　　　or update (when the new cost is lower) its cost if it is in the front group

So in one loop:

1. only one node is added into visited group;

2. all the nodes directly connected with the visited group are added into front group;

3. update on some of the front nodes (connected with newly added nodes in visited), should be made.

　 For 3, alternatively, we can just add the new nodes connected with the newly added visited node (not update, so may have copy of the same node in front). Then right after we add a visited node, we should "skip" the copy of this visited node in front group.

To improve the algorithm's efficiency, we can implement the front group by Heap data strucutre, instead of searching the minimum element in list with O(N) for each loop.

During each loop, we first pop the minimum node from front group and set it as visited, then we push back newly added front nodes connected with this new visited node, to reach a O(logN) complexity.

巴特西

Dijkstra 算法

最新文章

热门文章