Java实现几种最短路径问题

前言

最短路径问题在现实处处可见,而且针对不同的情形都需要具体分析才会找到最好解法。

最短路径Floyd算法

一支部队急行军,要经过A,B,C,D据点,这四个据点之间有些之间有路到达,有些没有。为了最大的节约时间,部队指挥部需要知道任意两个据点之间的最短时间。以下是两两之间所花的时间(如下图所示):

那么如何才能让两个据点之间花的时间变短?加入第三个据点即可。因此判断条件就出来了:
两个据点之间花费的时间如果比加入第三个据点的时间长,那么两个据点之间的最短时间即是加入第三个据点的时间之和。
这样Floyd算法的Java实现如下(核心代码就是上面的判断,边的权值全部提前赋值):

Floyd算法容易理解,并且可以算出任意两个点之间的最短距离。不难得出,Floyd算法的时间复杂度为O(n3),空间复杂度为O(n2),n为顶点的个数。

单源最短路径Dijkstra

还有一种常见的问题,也就是单源最短路径。求出1号顶点到其它顶点的最短距离:

类似Floyd算法,我们在核心代码里面直接就给出图的邻接矩阵,避免不必要的代码。

该算法同样和顶点关系密切,其时间复杂度为O(n2),空间复杂度也只需要存储图的邻接矩阵或者邻接链表即可。

0

发表评论

邮箱地址不会被公开。