在计算机算法问题的研究中，最短路径问题是一个非常经典的问题。这个问题主要研究的是在给定的一张由多个顶点以及多条连接边构成的图中，从某一个点出发,需要找到到达其他每一个点的最短路径。在实际生活中，就好像是你搬家搬到了一个新的位置，你如何选择出最佳路线，去菜市场、学校、医院都能够最为方便。往大了说，百度地图的静态位置规划最优路线也是一样的原理，从当前位置出发，分别规划出去多个目标目的地的最优路线。
那么，该如何解决这个问题呢，在计算机科学里面创立了一种称之为Dijkstra算法的方法。它是由注明计算机科学家Dijkstra命名的。假设我们的目标地点是四个：菜市场、学校、医院、地铁站，我们的起点是家。从家里都有直接的路到达菜市场、学校、医院（注意这些路只是直接到达的路，并不是距离上最为短的路）。而想要到地铁站，则必须要经过菜市场、学校或者医院。
那么在这张简化版的地图上，就首先有了三条路径，分别是：家->菜市场、家->学校、家->医院。接下来考虑一下这三条路径中最短的一条，为家->菜市场。有了这条最短的，我们可以下一个定论了：从家到菜市场一定是直接到达的这条路最短，为什么呢？因为如果我们绕路到菜市场的话，因为从家出发到菜市场是从家出发直接到达的地点中最短的，我们到其他点的距离就已经比我们直接到菜市场的路要远了，然后再绕到菜市场，这一定不是最优的。OK，这样，我们完成了第一步，那就是找到了到菜市场的最优路径。同时，更新一下去各个地方的路径长度：
家->菜市场：2
家->学校：3
家->医院：4
家->地铁站：暂时没找到路
接下来呢，我们改变起点，以菜市场为起点去找，正好呢，以菜市场为起点，有一条通往地铁站的路。这样呢，我们从家到地铁站就暂定出了一条路线，先从家到菜市场，再从菜市场到地铁站。更新一下表：
家->菜市场：2
家->学校：3
家->医院：4
家->地铁站：2+3=5
这个时候，由于菜市场只有一条到地铁站的路，所以菜市场可以不用考虑了。记下来家到菜市场的最短路径为2即可。
家->菜市场：2 （已找到最优路径）
家->学校：3
家->医院：4
家->地铁站：5
此时，我们考虑学校这个点，它是目前路径表中最小的，如果不走从家直接到学校的路， 而是先到别的地方再绕到学校，那么肯定比直接到学校要远。所以，从家到学校的最短路径没有问题，就是直接到学校。现在我们找到了家到学校的最短路径，接下来要访问学校这个点了。考虑以学校进行中转，家到地铁站路程缩短到4，家到医院缩短到3.8，学校能到的地方访问结束了，更新列表
家->菜市场：2 （已找到最优路径：家->菜市场）
家->学校：3 （已找到最佳路径：家->学校）
家->医院：3.8 （已找到最佳路径：家->学校->医院）
家->地铁站：4
接下来，我们能够很理直气壮的说家到医院最短的路一定是现在找到的，为什么呢，如果不走这条路，而选择从地铁站绕，那么肯定比3.8远。接下来，我们在去访问医院这个点，如果以医院为中转，从家到地铁站需要9，比现有的4还要大，所以不是最佳路径。
这样子，我们把家到每一个点的最佳路径都找到了：
家->菜市场：2 （已找到最优路径：家->菜市场）
家->学校：3 （已找到最佳路径：家->学校）
家->医院：3.8 （已找到最佳路径：家->学校->医院）
家->地铁站：4 （已找到最佳路径：家->学校->地铁站）
再总结一下整个算法的过程：首先，从起点开始，构建一张起点能够到达的距离列表，然后从起点找一条最短能到达的路径，能到达的那个点和这条最短直达路径就是到这个点的最短路径。然后访问这个已经被找到最短路径的点，通过它中转，更新从起点到各个点的距离列表。然后，再从这张表中选出最小的路径和对应的点，这条路径就是对应的点的最短路径。依次进行这个步骤，直到把每一个点的最短路径都找到。
从这个算法中，我感触最深的其实是思想并不复杂。其核心思想就是在现有基础上先把能获取到的信息获取到，把能做好的事情做好。然后有了一些改进和成果之后，再利用新获得的结果和反馈，获取更多有效信息，然后再次优化出结果。就这样反复进行迭代和优化，最终完成的结果越多，获得的信息和反馈就越多和越准确，逐渐就能一步步解决整个问题。
其实，这就跟我们常说的“小步快跑”思想非常一致，当一件事情非常棘手的时候，不妨先利用好手头的信息和资源，先做起来，把能做的事情做好。“天助自助者”，当你做出了一点成果之后，你就能得到更多的信息和反馈，帮助你再进一步解决问题。很多时候，哪怕是伟大的专家，它能想出来的方法也是一开始看上去“很笨”的，但是只要你动手开始做了，不再犹豫不决了，你就能够获取到更多信息。
所以，怎样找到最短路径呢？这个路径可不仅仅是计算机算法上的路径哦，也可以是实现人生理想和目标的路径，本质上就是一个办法：先赶紧做起来，行动起来，把手头上能利用的资源利用好，边做边得到反馈，边做边进行优化！有时候，学习之后的大彻大悟会让人觉得：科学道理和人生哲理本质上是多么的相似啊！
网友评论