图的应用：最短路径
上篇文章的最小生成树有没有意犹未尽的感觉呀？不知道大家掌握得怎么样，是不是搞清楚了普里姆和克鲁斯卡尔这两种算法的原理了呢？面试的时候如果你写不出，至少得说出个大概来吧，当然，如果你是要考研的学生，那就要深入的理解并且记住整个算法的代码了。
什么是最短路径
今天我们学习的是图的应用中另外一个经典的问题，也就是 最短路径 的问题。这个问题和最小生成树是不同的，最小生成树的要求是要连通所有的结点，并且走得是权值最小的那条路线。而最短路径则是指的从某个顶点到另一个顶点中权值最小的那条路径。这条路径不一定是包含在最小生成树中的，所以它们并没有太大的联系。
从这张图来看，我们从结点 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小时了（当然，这只是例子，大家在非高铁的情况下肯定还是更多地会选择起始站的火车来坐）。
多源最短路径 Floyd 算法
首先，我们先说一个多源最短路径的算法。那么什么叫做多源呢？
其实就是这一个算法就能够得出所有结点到所有结点之间的最短路径。没错，就这一个算法，不管哪个结点到哪个结点，它们之间的最短路径都一次性算出来了。神奇吗？不不不，更神奇的，而且你一会就会叫出 Oh!My God! 的是它的核心代码，只有五行！！
function Floyd($graphArr){
$n = count($graphArr);
for($k = 1;$k<=$n;$k++){ // 设 k 为经过的结点
for($i = 1;$i<=$n;$i++){
<strong style="color:transparent">本&文来源gao@daima#com搞(%代@#码网@</strong><textarea>搞gaodaima代码</textarea> for($j = 1;$j<=$n;$j++){
// 如果经过 k 结点 能使 i 到 j 的路径变短，那么将 i 到 j 之间的更新为通过 k 中转之后的结果
if($graphArr[$i][$j] > $graphArr[$i][$k] + $graphArr[$k][$j]){
$graphArr[$i][$j] = $graphArr[$i][$k] + $graphArr[$k][$j];
}
}
}
}
for($i = 1;$i<=$n;$i++){
for($j = 1;$j<=$n;$j++){
echo $graphArr[$i][$j], ' ';
}
echo PHP_EOL;
}
}
// 请输入结点数：4
// 请输入边数：8
// 请输入边，格式为 出 入 权：1 2 2
// 请输入边，格式为 出 入 权：1 3 6
// 请输入边，格式为 出 入 权：1 4 4
// 请输入边，格式为 出 入 权：2 3 3
// 请输入边，格式为 出 入 权：3 1 7
// 请输入边，格式为 出 入 权：3 4 1
// 请输入边，格式为 出 入 权：4 1 5
// 请输入边，格式为 出 入 权：4 3 12
// 0 2 5 4
// 9 0 3 4
// 6 8 0 1
// 5 7 10 0
转载请注明原文链接：PHP数据结构-图的应用：最短路径
