从A地到B地有多条路径可以到达,现要从A地到B地运物资,设计一个求走那条路径最短的算法,这个题目用了哪些数据结构?大致的算法思想是什么?
这个问题可以用图论来解决。图论是一门研究图形结构的数学分支,可以用来描述网络、流程、导航等问题。
具体来说,这个问题可以用有向图来表示,其中每个地点对应一个图中的结点,每条路径对应一条有向边。要求求出A地到B地的最短路径,就可以使用最短路径算法来解决。
最短路径算法有很多种,常用的有贪心算法和动态规划算法。这里介绍一种经典的最短路径算法——迪杰斯特拉算法。
迪杰斯特拉算法的基本思想是从起点开始,每次找到一条到达不同结点的最短路径,直到找到终点为止。
算法步骤如下:
初始化:将起点设为已经访问过,并将起点到其它所有结点的距离设为无穷大(或某个极大值)。
更新距离:遍历起点的所有出边,更新从起点出发能够到达的结点的距离值。如果从起点到某个结点的距离加上从该结点到另一个结点的距离,则更新从起点到该结点的距离为前者。
找到最近结点:从未访问过的结点中找到离起点最近的结点,将其设为已访问过。
重复步骤2和步骤3,直到找到终点为止。
算法结束后,起点到终点的距离即为从起点到终点的最短路径。
举个例子,假设有一张图如下:
A ---3---> B ---2---> C
| /
1 /
| /
v /
D ---2---> E
起点为A,终点为E。
首先将A设为已访问过,并将A到其它所有结点的距离设为无穷大。
然后更新距离。遍历A的出边,可以发现A到B的距离为3,A到D的距离为1。将这两条路径的距离设为3和1。
接下来找到最近结点。可以发现A到D的距离最小,因此将D设为已访问过。
然后更新距离。遍历D的出边,可以发现A到D到E的距离为3,比A到E的距离小,因此将A到E的距离更新为3。
找到最近结点,发现A到E的距离最小,因此将E设为已访问过。由于E是终点,因此算法结束。
最终,A到E的距离为3,即为A到E的最短路径。
在迪杰斯特拉算法中,需要用到一些数据结构来存储图的信息。通常可以使用邻接矩阵或邻接表来表示图,也可以使用堆来优化算法的执行效率。
就是计算从A到B所以可能性的路径的权值,然后,取权值最小的那条路径