Java – 在距离加权映射中找到2个点之间的最短路径

我需要一种算法来查找地图中两点之间的最短路径，其中道路距离由数字表示。

给出的内容：开始城市目的地城市Z.

城市间距离列表：

A – B：10
F – K：23
R – M：8
K – O：40
Z – P：18
J – K：25
D – B：11
M – A：8
P – R：15

我以为我可以使用Dijkstra的算法，但它找到了到所有目的地的最短距离。 不只是一个。

任何建议表示赞赏。

Answer 1

就像SplinterReality所说： There's no reason not to use Dijkstra's algorithm here.

下面的代码我从这里开始修改并修改它以解决问题中的示例。

 import java.util.PriorityQueue; import java.util.List; import java.util.ArrayList; import java.util.Collections; class Vertex implements Comparable { public final String name; public Edge[] adjacencies; public double minDistance = Double.POSITIVE_INFINITY; public Vertex previous; public Vertex(String argName) { name = argName; } public String toString() { return name; } public int compareTo(Vertex other) { return Double.compare(minDistance, other.minDistance); } } class Edge { public final Vertex target; public final double weight; public Edge(Vertex argTarget, double argWeight) { target = argTarget; weight = argWeight; } } public class Dijkstra { public static void computePaths(Vertex source) { source.minDistance = 0.; PriorityQueue vertexQueue = new PriorityQueue(); vertexQueue.add(source); while (!vertexQueue.isEmpty()) { Vertex u = vertexQueue.poll(); // Visit each edge exiting u for (Edge e : u.adjacencies) { Vertex v = e.target; double weight = e.weight; double distanceThroughU = u.minDistance + weight; if (distanceThroughU < v.minDistance) { vertexQueue.remove(v); v.minDistance = distanceThroughU ; v.previous = u; vertexQueue.add(v); } } } } public static List getShortestPathTo(Vertex target) { List path = new ArrayList(); for (Vertex vertex = target; vertex != null; vertex = vertex.previous) path.add(vertex); Collections.reverse(path); return path; } public static void main(String[] args) { // mark all the vertices Vertex A = new Vertex("A"); Vertex B = new Vertex("B"); Vertex D = new Vertex("D"); Vertex F = new Vertex("F"); Vertex K = new Vertex("K"); Vertex J = new Vertex("J"); Vertex M = new Vertex("M"); Vertex O = new Vertex("O"); Vertex P = new Vertex("P"); Vertex R = new Vertex("R"); Vertex Z = new Vertex("Z"); // set the edges and weight A.adjacencies = new Edge[]{ new Edge(M, 8) }; B.adjacencies = new Edge[]{ new Edge(D, 11) }; D.adjacencies = new Edge[]{ new Edge(B, 11) }; F.adjacencies = new Edge[]{ new Edge(K, 23) }; K.adjacencies = new Edge[]{ new Edge(O, 40) }; J.adjacencies = new Edge[]{ new Edge(K, 25) }; M.adjacencies = new Edge[]{ new Edge(R, 8) }; O.adjacencies = new Edge[]{ new Edge(K, 40) }; P.adjacencies = new Edge[]{ new Edge(Z, 18) }; R.adjacencies = new Edge[]{ new Edge(P, 15) }; Z.adjacencies = new Edge[]{ new Edge(P, 18) }; computePaths(A); // run Dijkstra System.out.println("Distance to " + Z + ": " + Z.minDistance); List path = getShortestPathTo(Z); System.out.println("Path: " + path); } } 

上面的代码产生：

 Distance to Z: 49.0 Path: [A, M, R, P, Z] 

Answer 2

估计的sanjan：

Dijkstra算法背后的想法是以有序的方式探索图的所有节点。 该算法存储优先级队列，其中节点根据开始时的成本排序，并且在算法的每次迭代中执行以下操作：

1. 从队列中提取从一开始就具有最低成本的节点N.
2. 获取其邻居（N’）及其相关成本，即成本（N）+成本（N，N’）
3. 在队列中插入邻居节点N’，优先级由其成本给出

确实，该算法计算起点（在您的情况下为A）与所有其余节点之间的路径成本，但您可以在算法到达目标时停止探索算法（在您的示例中为Z）。 此时，您知道A和Z之间的成本以及连接它们的路径。

我建议你使用一个实现这个算法的库，而不是自己编写代码。 在Java中，您可以查看一下Hipster库 ，它有一种非常友好的方式来生成图形并开始使用搜索算法。

这里有一个如何定义图形并开始使用Dijstra with Hipster的示例。

 // Create a simple weighted directed graph with Hipster where // vertices are Strings and edge values are just doubles HipsterDirectedGraph graph = GraphBuilder.create() .connect("A").to("B").withEdge(4d) .connect("A").to("C").withEdge(2d) .connect("B").to("C").withEdge(5d) .connect("B").to("D").withEdge(10d) .connect("C").to("E").withEdge(3d) .connect("D").to("F").withEdge(11d) .connect("E").to("D").withEdge(4d) .buildDirectedGraph(); // Create the search problem. For graph problems, just use // the GraphSearchProblem util class to generate the problem with ease. SearchProblem p = GraphSearchProblem .startingFrom("A") .in(graph) .takeCostsFromEdges() .build(); // Search the shortest path from "A" to "F" System.out.println(Hipster.createDijkstra(p).search("F")); 

您只需要替换您自己的图形定义，然后像示例中那样实例化算法。

我希望这有帮助！

Answer 3

这可能为时已晚，但没有人提供算法如何工作的清晰解释

Dijkstra的想法很简单，让我用下面的伪代码来展示它。

Dijkstra将所有节点分成两个不同的集合。 不安和定居。 最初所有节点都在未结算的集合中，例如它们必须仍然被评估。

首先，只将源节点放入已设置的locateNodes集中。 如果找到从源到特定节点的最短路径，则特定节点将移动到已设置的集合。

算法运行，直到unsettledNodes设置为空。 在每次迭代中，它从未设置的节点集中选择与源节点的距离最小的节点。 例如，它读取从源传出的所有边，并从尚未确定的这些边评估每个目标节点。

如果在使用所选边缘时可以减少从源到该节点的已知距离，则更新距离并将节点添加到需要评估的节点。

请注意，Dijkstra还确定了每个节点前往源的前inheritance者。 我把它从伪代码中删除了以简化它。

Lars Vogel的致谢

Answer 4

维护可以前往的节点列表，按起始节点的距离排序。 在开始时，只有您的起始节点将在列表中。

当您尚未到达目的地时：访问距离起始节点最近的节点，这将是排序列表中的第一个节点。 当您访问节点时，将其所有相邻节点添加到列表中，除了您已访问过的节点。 重复！