我有一个图表,我需要找到从多个源到单个目的地的距离.我知道如何使用dijkstra算法找到单一来源到多目的地.
我在这里找到了一个可接受的答案:贝尔曼 - 福特这样的算法,只适用于多个启动,单一目的地？
但我不明白它为什么会起作用.谁有人解释为什么这个答案有效？
它的工作原理是因为如果你有一个(原始)源s和你的目标t- 在修改后的图形中,你会反转边缘并找到从t所有节点到最短路径,包括到s.
这条路是 t->v1->v2->...->vk->s
当且仅当原始图中存在边时,此路径中的每条边(u,v)都存在(v,u),因此反转图中的上述路径可以直接转换为路径:
s->vk->vk-1->...->v2->v1->t
路径的权重是相同的,并且没有更短的路径,否则 - 您将在反转图上找到它.
作为旁注,我个人更喜欢通过创建一个新的虚拟节点将多个源问题转换为单一来源问题x,并从x权重为0 x的任何源创建边缘,然后运行最短路径算法作为源.
(假设你需要的是从某个源到目标的最短路径)