Bi Directional Dijkstra

双向Dijkstra

问题

给定具有非负边权重的图形，一个源顶点s和目标vertec t 。找到S和T之间的最短路径

但是，为什么我们不只是使用Dijkstra的算法来解决问题呢？

0（E + VLOGV）是Dijkstra算法最糟糕的时间复杂性，该算法非常快。但是，对于具有2000万个顶点和5000万个边缘的图表，它平均可以工作几秒钟。因此，我们需要更快的东西。

在进行双向搜索的细节之前，让我们探索“六个分离程度”的概念

• 1929年，匈牙利作家Frigyes Karinthy首次在他的短篇小说链中提出了“六度分离”的概念。
• 六个分离的想法是，世界上所有的生物和其他所有事物都彼此六分之六或更少。

现在，让我们查看最受欢迎的社交网络Facebook。假设Facebook上的一个普通人大约有100个朋友。然后，如果我们考虑那个人的朋友的朋友，那就是100*100，即10,000个朋友的朋友。如果我们考虑“朋友的朋友的朋友” ，那将是100万倍或100万倍。如果我们继续六次，我们将有1卢比的人。

但是，全球人口为76亿。

现在，我们如何通过社交网络上的连接找到两个随机的人A和B之间的最短路径？

让我们考虑双向搜索。因此，我们将考虑B的朋友的朋友和B的朋友的朋友。

请注意，我们将有大约100万个朋友的朋友的朋友和B的朋友朋友。因此，在这种情况下，我们总共只考虑200万人。

普通的Dijkstra的算法必须在社交网络上看大约2亿人，以找到A和B之间的最短路径。

什么是双向搜索

在此，我们同时进行了两个同时搜索：一个从初始状态前进，一个从目标向后进行，当两者在中间相遇时停止。

图G上的双向dijkstra的伪代码g

• 构建GR（反向图）
• 从G中的S（源）和GR中的T（target）启动Dijkstra
• 在G和GR中的Dijkstra步骤之间的交替
• 当在G和GR中处理某个顶点“ V”时停止。
• 计算S和T之间的最短路径。

S和T之间的最短路径的计算是从G中的S向前dijkstra中的距离估计值。让Dister [u]是gr中T的向后dijkstra中的距离估计值。在G和GR中处理了一些节点“ V”之后，从S到T的最短路径通过了一些节点“ U”，该节点在G，GR或GR中进行处理， D（S，T）= Dist [U] + ISTR [U]