算法|计算汽车路程最短路径

欢迎点击「算法与编程之美」↑关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

有以下一个问题：

每条道路长度相同，从顶点1到顶点9如何求得其最短路径。

首先，我们可以将矩阵简化成：

此矩阵顶点1到顶点4的最短路径为2（每条道路长度为1），此时唯一2条道路（1—2—4和1—3—4）的长度相同，同时都为最短路径，通过观察其规律，我们可以发现，先从水平方向走到与终点横坐标相同的点，在从垂直方向走到终点或先从垂直方向走到与终点竖坐标相同的点，在从水平方向走到终点即为最短路径。

我们可以看开始的这个矩阵

用上述方法，也能够求得其最短路径（也可先走一部分水平方向在走垂直方向或先走一部分垂直方向在走水平方向其最短路径都相同），所以n*n的最短路径就为2n。

根据以上描述，我们可以写出代码：

此文章有浅入深讲解了求取路径最短的方法，求取最短路径的方法有很多种，本文就其中一种做了讲解，如需了解更多求取最短路径的方法，可参考其他博客。

更多精彩文章：