PHP数据结构-图的应用：最短路径

图的应用：最短路径

上篇文章的最小生成树有没有意犹未尽的感觉呀？不知道大家掌握得怎么样，是不是搞清楚了普里姆和克鲁斯卡尔这两种算法的原理了呢？面试的时候如果你写不出，至少得说出个大概来吧，当然，如果你是要考研的学生，那就要深入的理解并且记住整个算法的代码了。

活动：慈云数据爆款香港服务器，CTG+CN2高速带宽、快速稳定、平均延迟10+ms 速度快，免备案，每月仅需19元！！ 点击查看

什么是最短路径

今天我们学习的是图的应用中另外一个经典的问题，也就是 最短路径 的问题。这个问题和最小生成树是不同的，最小生成树的要求是要连通所有的结点，并且走得是权值最小的那条路线。而最短路径则是指的从某个顶点到另一个顶点中权值最小的那条路径。这条路径不一定是包含在最小生成树中的，所以它们并没有太大的联系。

从这张图来看，我们从结点 1 到结点 2 的最短路径是 2 ，这个很明显。那么从结点 1 到结点 3 呢？可不是直接的中间那个权值为 6 的路径，而是走 1->2->3 这条路径，也就是权值加起来为 5 的这条路径。

然后我们再来看结点 3 ，它到结点 1 最短路径应该是走 3->4->1 这条路径，也就是权值为 6 的这条路径，而不是中间的那条直线的权值为 7 的路径。

没错，这就是最短路径的概念了。在最短路径中，我们一般会解决单向图的问题，但实际生活中呢？最典型的地图相关的应用其实是都是双向图的。不过这并不影响我们的学习，我们可以把这个示例图中的结点看成是城市火车站点，就算是连接结点 1 和结点 3 的火车线路，也不一定来去的时间都是相同的。比如说从长沙到北京的 Z2 次火车全部运行时间为14小时42分，而回来的 Z1 次则是14小时10分。那么我们是否可以选择其它的火车，比如有趟火车从长沙到石家庄可能只需要8小时，然后从石家庄到北京只需要2小时，这样我们选择这条线路的总时间就只需要10小时了（当然，这只是例子，大家在非高铁的情况下肯定还是

本文来源网站：info110.com，若侵权，请联系删除。

《PHP数据结构-图的应用：最短路径》来自互联网同行内容，若有侵权，请联系我们删除！