-1

我正在开发一个简单的程序来计算从一个城市到另一个城市的最短路径,使用图形的有向加权节点来表示火车轨迹图。

到目前为止,我尝试了、Bellman-Ford和算法,所有这些算法都很好地找到了与起点不同的不同目的地的最短路径。DijkstraFloyd-WarshallJohnson

但是当我需要计算城市 A 和通过其他城市返回城市 A 之间的路径时,我总是得到 0 值,因为这些方法忽略了从城市到自身的路径,以免陷入无限循环。

我知道通过创建另一个参数来解决该循环问题可能很简单,该参数target旨在使算法在捕获此目标节点时停止,但我没有修改其中一个库的技能。

谁能给我指路?

我的图表是和toAB5 - BC4 - CD8 - DC8 - DE6 - AD5 - CE2 - EB3 - AE7的距离应该是,但在所有这些算法中它正在返回。BB90

注意:它不是重复的,因为到目前为止,没有人会在开始时寻找路线的尽头,因为我在 StackOverflow 和 Google 上搜索过,至少在 Java 中是这样。

4

1 回答 1

0

一种简单的方法是使用您已经拥有的最短路径算法/库和修改后的图。您可以复制每个节点和相应的相邻出边,然后找到从复制节点到原始节点的最短路径。

以下是 AA 路径的转换效果(为简单起见,没有权重):

图形示例

于 2013-08-27T21:27:12.823 回答