yuxinzhu / search Goto Github PK

这里直接取出当前代价最小的点，对于它的所有相邻点，判断其是否被访问过，如果访问过就加入“已访问”集合，更新一下优先队列，认为这样就是到达这个点最优解。
但是这样似乎不太正确。例如点C邻接A和B，A->C代价100，B->C代价1，而在优先队列中，root->A代价1，root->B代价2，那么该算法应该会先取出队列中的A，然后发现邻接的C没有访问，于是记录C已经被访问，然后得到路径root->A->C，代价101；实际上，root->B->C代价只有3。
应该改成类似Dijkstra的形式，优先队列中存的结点都应该是可访问但未访问的，然后从这里面挑选出最小代价者，并且更新数据。

Here the algo retrieves the first node P in the priority queue(which has the least cost), and for each adjacent node Q of P, if Q has not been visited yet, mark Q as 'visited'(or add Q into set 'visited'). Meanwhile, record P to Q as an edge of the best (or least cost) path for root to reach Q.
But I think that algo has a bug. For example, node C is an adjacent node of node A and node B. The cost from A to C is 100 and from B to C is 1. Suppose that till now A and B have been visited, the least cost from root to A is 1 while from root to B is 2, and A and B is in the priority queue. The algo will certainly retrieve node A from queue coz its lower cost than B and will mark C as 'visited', then consider that from root to C bypass A is the best path. But in fact, root->A->C cost 101 while root->B->C only cost 3, which means the latter path is better than the 'best' path according to the algo.
I think an convenient way to fix the bug is using Dijkstra algo, which is quite similar to the current algo.
Sorry for my bad translation.