如何计算图形中源和目标相同的两个节点之间的最短路径？

图：

A->B(5) 
A->D(5) 
A->E(7) 
B->C(4) 
C->D(8) 
C->E(2) 
D->C(8) 
D->E(6) 
E->B(3)

例如什么是B和B之间的最短路径？我试图使用dijkstra但没有工作，它总是在第一步中返回B-> B。

正确ANS：B-> C-> E->乙

难道你不能问“从X-> B的最短路径是什么？”对于存在边B-> X的任何节点X，取其中的最小值，并添加B-> X？ – DSM 2012-04-13 03:18:48

分割顶点为两个：B1和B2，在那里，在乙在原始图发表的所有边缘将在B1开始;以B结尾的所有边将在B2中终止。

之后，您可以运行Dijkstra以找到修改图中从B1到B2的最短路径。

注意：如果要保留图中的所有路径，请添加额外的边B2-> B1。这不会改变你的循环搜索的结果，并且原始和修改图表中的所有路径将是等效的

2012-04-13 07:57:38 voidengine

回答