图的最短路问题

聊到图论，最短路是个绕不开的坎。别看它名字简单，里面的门道可不少。不管是面试还是实际应用（比如地图导航、网络路由），这玩意儿都极其重要。 很多时候我们看到一个算法题，如果没有思路，第一反应是啥？暴力枚举呗。那最短路的暴力解法是啥？把从起点到终点的所有可能路径都列出来，然后一个个算它们的权重和，最后取个最小值。 想法很简单，但你稍微画个图就知道，一个稍微复杂点的图，路径的数量就是指数级爆炸，这谁顶得住？所以，暴力解法咱们心里有数就行了，它只能作为思考的起点，根本没法写。 今天，咱们就从正经的解法开...