最短路径

来自计算思维百科
跳转至: 导航搜索
最短路径1.png

在一幅图中,我们往往需要从一个点出发到达目标点,途中所经过的路径有长有短,我们希望能选择一条最短的路径到达,这条路径就称为最短路径。

基本概念

最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括:

确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。

确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

确定起点终点的最短路径问题 - 即已知起点和终点,求两结点之间的最短路径。

全局最短路径问题 - 求图中所有的最短路径。

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。

应用范围

最短路径问题可以直接用于解决许多问题,诸如各种管道铺设、线路安排、厂区布局、设备更新、物流配送等等。

使用方法及步骤

最短路径的主要思想是首先把问题抽象成网络图,然后从源点求出下一节点长度最短的一条路径,再通过对路径长度迭代得到从源点到其他目标节点的最短路径。

应用案例

寻找物流配送路径

案例:

基于电子商务不受时间、地域的限制,配送任务复杂而繁琐,成本居高不下,于是电子商务公司考虑配送成本,尽量控制销售商品的配送范围,使之相对集中且形成规模。另一方面,物流公司应积极协作,选择最短路径作为配送路径降低成本,开源节流,降低物流成本和配送服务的价格,利于持续发展。下面以从城市v1到城市v6为例,求最短路径。

解决步骤:

首先,根据实际情况作出城市v1到城市v6的网络图,每条路径为图中的边,边上的权数表示该段路径的长度,然后作出该网络图的距离矩阵。从两个代表城市的距离的权矩阵开始,每次插入一个城市点比较任意两点间的已知最短路径和插入城市点作为中间顶点时可能产生的路径距离,然后取较小值以得到新的距离权矩阵。当所有城市点均作为顶点时,得到的最后的权矩阵就反映了所有顶点间最短距离信息。最短距离者作为最少费用者。

最短路径2.png

最短路径3.png

根据距离矩阵逆向追踪得最短路线:v1->v3->v2->v4->v5->v6;最短距离为12。

可以体现的计算思维

最短路径法体现了计算思维中的折中及抽象的思想,在解决问题的时候,需要在多个因素中进行权衡,同时也结合图的思想,把问题抽象成图,从纷繁中提炼出问题的本质,从而使问题易于解决。