algorithm - 需要用最小权重检测图中的结束路径

Question

想找到从节点a到任意节点的最短加权路径。未给出目标节点。可以多次访问任何顶点。

如果路径权重应该小于 Integer.MAX

继续进行的算法是什么？？无法检测算法本身。

我确实尝试过旅行推销员问题，但它不匹配；它既不适合 Dijkstra ...

如何将所有路径保存在内存中是这里的主要挑战..

编辑:图不是有向图，也没有负权重。

引用文献:http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare http://en.wikipedia.org/wiki/Travelling_salesman_problem

Answer 1

对于没有负权重的无向图，可以使用 Floyd-Warshall寻找时间复杂度为 O(V^3) 的所有对最短路径的算法，其中 V 是顶点数。该算法还提供了一种简单的方法来 reconstruct the all computed shortest paths .它使用 O(V^2) 内存来存储距离和用于重建路径的附加信息。

还有一些other algorithms以更好的时间复杂度解决这个问题，但 Floyd-Warshall 真的很容易编码和开始。