图中两个节点之间的最短路径（Java）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1226450/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Shortest path between two nodes in a graph (Java)
提问by Billy Bob Bain
I have a program with a graph whose nodes represent some processes, and the proccess computing time is the node's cost.This graph is maintainded in memory as a list of nodes and each nod has a list of parent and children, and his execution time.
我有一个带有图的程序，它的节点代表一些进程，进程计算时间是节点的成本。这个图作为节点列表在内存中维护，每个节点都有一个父节点和子节点的列表，以及他的执行时间。
I must find the path with the minimum execution time.
我必须找到最短执行时间的路径。
- Each node can connect with any other.
- There is only one start node and one end node.
- One node can have various "parent" and "children"
- 每个节点都可以与任何其他节点连接。
- 只有一个开始节点和一个结束节点。
- 一个节点可以有不同的“父”和“子”
Can someone tell me the best way to do this?
有人可以告诉我这样做的最佳方法吗？
回答by sepp2k
You can use Dijkstra's Algorithmfor this.
您可以为此使用Dijkstra 算法。
回答by Robert Petermeier
Dijkstrahas been mentioned already, there is also the A* algorithmwhich can be better performance-wise under certain conditions and from which one can learn a lot. There is also a good book on graph algorithms with lots of Java code examples by Robert Sedgewick which I found useful several years ago. The title is "Algorithms in Java, Part 5: Graph Algorithms".
Dijkstra已经提到过，还有一种 A* 算法，它可以在某些条件下在性能方面更好，并且可以从中学到很多东西。还有一本关于图算法的好书，里面有很多由 Robert Sedgewick 写的 Java 代码示例，我几年前发现它很有用。标题是“Java 中的算法，第 5 部分：图算法”。
回答by Extrakun
One way to do this is by using various shortest path algorithm, such as Dijkstra's algorithm. For this to work, you would need to code a 'heap', a data structure in which the node with the smallest weight-age is on the top.
一种方法是使用各种最短路径算法，例如Dijkstra 算法。为此，您需要编写一个“堆”，这是一种数据结构，其中具有最小权重年龄的节点位于顶部。
The idea behind the algorithm is to keep track of the overall distance from the start to the current node for the current route. The usual greedy algorithm is one where you just select the neighbouring node with the shortest path. Dijkstra expands on this by picking the node which would give the shortest overall distance from the start node to that node.
该算法背后的想法是跟踪当前路线从起点到当前节点的总距离。通常的贪心算法是您只选择具有最短路径的相邻节点的算法。Dijkstra 通过选择将从起始节点到该节点的总距离最短的节点对此进行扩展。
回答by Billy Bob Bain
JGraph has an implementation of the Dijkstra algorithm.
JGraph 有一个Dijkstra 算法的实现。
回答by elhoim
Some notes specificly on Dijkstra algorithm in Java:
关于 Java 中 Dijkstra 算法的一些说明：
http://renaud.waldura.com/doc/java/dijkstra/
http://renaud.waldura.com/doc/java/dijkstra/
And a note about performance:
还有一个关于性能的说明：
The complexity of Dijkstra's algorithm depends heavily on the complexity of the priority queue Q. If this queue is implemented naively as I first introduced it (i.e. it is re-ordered at every iteration to find the mininum node), the algorithm performs in O(n2), where n is the number of nodes in the graph.
With a real priority queue kept ordered at all times, as we implemented it, the complexity averages O(n log m). The logarithm function stems from the collections PriorityQueue class, a heap implementation which performs in log(m). With a real priority queue kept ordered at all times, as we implemented it, the complexity averages O(n log m).
Dijkstra 算法的复杂性在很大程度上取决于优先级队列 Q 的复杂性。如果这个队列像我第一次介绍的那样天真地实现（即它在每次迭代时重新排序以找到最小节点），算法的执行时间为 O( n2)，其中 n 是图中的节点数。
当我们实现它时，真正的优先级队列始终保持有序，平均复杂度为 O(n log m)。对数函数源于集合 PriorityQueue 类，这是一个在 log(m) 中执行的堆实现。当我们实现它时，真正的优先级队列始终保持有序，平均复杂度为 O(n log m)。
