dijkstra
dist[i] 数组存储节点i到节点1之间,当前的最短距离。
每次迭代,选择dist[]最小并且未被收录的节点对应的边,因为只有代价最小的边白不回发生被其他更小的路径截的情况,只有在这种情况下,这个dist确实是真实的最小路径。
换言之,此时之所以不选择某条边E及其出点V并入集合,是因为有其余代价更小的边可以被选择并且这些代价更小的边有可能以更小的代价代替边E到达顶点V.
如果,最终的结果确实是要通过边E到达V生成最短路径,那么,随着越来越多的边被收录进集合中,边的权值(代价)越来越大,而顶点V也一直没有被收录进入集合中,直到有一刻,这条原先看起来代价比较大的边E变成了当前未被收录的且代价最小的边,这时候我们可以确定再也不会出现代价更小的路径来到达顶点V,然后将E和V收录进入集合。
至此,小E同学终于如愿以偿进入集合,而且不会担心被其他路径代替,因为他自己已经是最小代价的路径了。。。。。
这个过程真是像极了大家一起内卷,把自己打造的性价比更高或更廉价,以进入心仪的某公司或某体制,直到自己的成本对老板而言越来越高而被裁掉,换成代价更小的韭菜。像极了35中年危机与末位淘汰机制有木有有木有。。。。 唯一的解决办法就是可选择的边更少一点代价整体更高一点,可是这真的很难啊有木有有木有。。。。。