您现在的位置:主页 > 365bet平台网址 > 正文内容

[坐在马桶上看算法]算法6:弗洛伊德最短路径算法只有5条线

作者:365bet滚球网 来源:365bet体育网 更新日期:2019-10-30 浏览次数:
暑假期间,孝阳到几个城市旅行。
如下所示,有些城市有道路,而另一些则没有。
小樽想在出发前知道两个城市前面最短的路线,以节省金钱和方便计划的旅行。
在上图中,在4个城市中有8条道路,并且道路上的数字表示道路的长度。
请注意,这些道路是单向的。
接下来,您需要请求两个城市之间的最短路径,即两个点之间的最短路径。
这个问题也被称为来自多个来源的最短路径问题。
在这里,您需要一个数据结构来存储图表信息。仍可以将其保存在4 * 4矩阵(2D矩阵e)中。
例如,如果从城市1到城市2的距离为2,则e[1][2]的值为2。
如果城市2无法到达城市4,则设置e[2][4]的值。
同样,在这里,例如,城市本身为0,[1][1]为0,如下所示:
让我们回到问题。您如何找到两点之间的最短路径?
先前的学习表明,可以通过搜索深度或宽度来找到两点之间的最短路径。
因此,深度或幅度搜索执行n2次。换句话说,每两点执行一次深度或幅度搜索,并且可以获得两点之间的最短路径。
但是还有其他方法吗?
让我们考虑一下。根据过去的经验,如果要缩短两个点之间的距离(例如,从顶点a到顶点b),则只能输入和传递第三个点(顶点k)。从顶点a到顶点b的原始路线。
那么,这个中继的顶点k是什么?
在某些情况下,不仅可能会路由单个点,还会路由两个或多个点,从而导致传输时间短。即a-k1-k2b-或a-k1-k2… -k-i… -b。
例如,上图中从第四城市到第三城市(4-3)的距离e[4][3]最初是12。
如果仅移动城市编号1(4-1-3),则距离将减小为11(e[4][1]+ e[1][3]= 5 + 6 = 11)。
实际上,城市1到3也可以通过城市2。从1号到3号到5号的距离会更短(e[1][2]+ e[2][3]= 2 + 3 = 5)
因此,在经过1号和2号两个城市的换乘时,从4号到3号的距离进一步减小到了10号。
此示例表明,每个顶点可以缩短其他两个顶点之间的距离。
现在让我们将这个问题概括为:
如果两点之间不允许有第三点,则这些城市之间的最短距离是初始距离:
否。如果只允许一个顶点通过并找到两点之间的最短距离,我应该如何请求?
确定e[i][1]+ e[1][j]是否小于e[i][j]。
e[i][j]表示从i的顶点到j的顶点的距离。
e[i][1]+ e[1][j]是从i的顶点到第一顶点的距离与从第一顶点到j顶点的距离之和。
其中,i是1?N循环,j是1?N循环。该代码实现如下:
对于(i = 1; ii ++)
对于(j = 1; jj ++)
是(e[i][j]e[i][1]+ e[1][j])
e[i][j]= e[i][1]+ e[1][j];