学步园

非负权单源最短路

1、最短路可以朴素枚举解决，但可以通过最优子结构，重叠子问题来提高效率

2、最优子结构：a->b的最短路 = min{ a->(b的邻接点)最短路 }   （反证法）

3、由确定的最短路，广搜邻接点并更新，得到的是可能成为最短路的情况。

若m、n都是可能成为最短路的情况，且m<n

则m的最短路情况，不可能由n作为中转站的情况 成为最终的最短路

∴在可能成为最短路的情况中，选取最小值作为已确定的最短路（不可能更新了）

4、堆优化，只不过是提高了取最小值的效率