dijkstra
更好的理解
主要思想:每次确定一个点的最短距离
我们将图分为2块,一块为最短距离确定的点集,一块为没有确定最短距离的点集,通过前者向后者拓展,来求得答案
我们将所有已经有dis数值的点加入堆,然后每次dis数值最小的它的dis值就是最终的dis距离,所以可以将其加入到距离确定点集中,并用这个点去更新与它直接相连的点的dis值
为什么每次dis数值最小的它的dis值就是最终的dis距离呢?
因为如果其余的dis来更新这个最小距离的话,一定比当前的答案,更劣,因为当前dis已经是最小的了