用于解决有权图最短路径
可以用于货币转换
Dijkstra's algorithm is not guaranteed to be correct for negative edges. It might work... but it isn't guaranteed to work.
Dijkstra 的算法不保证对负 Edge 是正确的。它可能有效……但不能保证有效。
Observe that once a vertex is popped off the Priority Queue, it is never re-added. Its distance is never re-updated. So, in other words, once a vertex is popped from the Priority Queue, we know the true shortest distance to that vertex from the source.
Dijkstra is however generally considered better in the absence of negative weight edges, as a typical binary heap priority queue implementation has