00:00
这是一个由多个节点多个连接的边组成的图,每条边有一个权重,代表这条边的长度。如果我们想从零出发到达四,那么最短的路径应该怎么走?最短的路径长度又是多少呢?节点?我们就来聊聊X算法。首先我们需要一张表格来记录节点零到所有节点的距离,初始时都是无穷大。另外,为了记录最短路径,需要记录最短路径中每个节点的前面的节点现在都会空。首先节点零自己到自己距离肯定是零,然后检查所有节点中距离最短的节点当然是自己了,把零标记为最优路径中的节点。接着更新节点零附近的节点一和节点七的距离分别是四和八。所以右边表格中可以将出发点零到节点一和节点七更新为四和八,把节点零作为节点一和节点七的。
01:00
前面节点,然后我们在未标记的节点中寻找距离出发点最小的节点是节点一,把它标记说路径最优路径节点中,尝试更新新标记的节点一的临近节点分别是节点二和节点七。首先节点一到节点二的边长是八,如果从零出发到二的最优路径是经过节点一的话,距离就是12小于无穷大。更新节点二的距离,节点二的前面点是节点一,然后我们来看节点七,假如从出发点零经过节点一到点七就是距离15,但是这个路径要大于节点七本来的距离,所以不更新。然后我们又在未标记的节点中寻找距离最小的节点是节点七,把它标记收录最优路径中,接着尝试更新临近的节点分别是。
02:00
点八和节点六,从出发点零经过节点七到达节点八的距离是15,到达节点六的距离是九,它们都比无穷大小更新距离,并且设置它们的前面点都是节点七,以此类推。我们可以把刚才的做法归结成两条步骤,第一,每次从未标记的节点中选择距离出发点最近的节点,标记收入到最优路径集合中。第二,计算刚加入的节点A的临近节点B的距离不包含标记的节点,如果节点A的距离加上节点A到节点B的边长之和小于原来节点B的距离,就更新节点B的距离和前面点。就这样循环,一直到目的地被标记,也就是找到从出发点到目的地的最短路径了。就按照这样的规则查找未标记中的最短距离是节点六添加。
03:00
它标记周路最右路径中尝试更新节点六临近的节点八和节点五。从出发点到节点六的距离是九,若经过六到五,那么节点五的距离就是11,温心无穷大截面点是节点六,而从出发点经过节点六到节点八的距离就是15,和原来一样就不更新了。我们加快点角度。接下来在未标记中寻找最短距离的节点是节点五,它的临近节点有三个,如果经过节点五到达这三个点,那么距离分别是十五二十五二十一,节点三和节点四。更新节点二不更新。接下来未标记中最短的节点是二,它的临近节点是节点八和节点三节点五,因为已经标记了,就不需要了。若经过节点二到达节点三,那么距离是19,更新原来的25。
04:00
前面点也要改为节点二了,若经过节点二到达节点八,距离变成14更新,然后最短距离的节点是八,临近节点都已标记,无需更新,然后最短的节点是三,更尝试更新未标记的节点四。若经过节点三,节点四的距离十二十八大于21,不更新了,最后把目的地节点四标记更新完毕,最终从出发点零到目的地节点四的最短距离是21。那么最短的路径该怎么走呢?我们根据前面点反过来追溯回去,首先节点四的前面是节点五,然后是六,然后是七,最后到达出发点零,那么这条路径就是最短路径了。大X转算法是从一个顶点到其余各顶点的最短路径算法。
05:00
节点边是有各自不同的权重,但都必须是正数,如果有负数,则需要beman four算法了。如果想要求任意两点之间的最短路径,那就需要用loy的算法了。
我来说两句