Java - 在一个带有距离权重的地图中找到两点间的最短路径

Question

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

已知信息： 起点城市A 目的地城市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算法，但它会找到所有目的地的最短距离，而不仅仅是一个。

欢迎提出任何建议。

- sanjan

---

这里没有任何理由不使用Dijkstra算法。它可以找到起点与所有终点之间的最短距离，然后你只需要从完成的结果列表或地图中选择你想要的目的地即可。 - SplinterReality

我认为在这种情况下不使用Dijkstra算法是有原因的。Dijkstra算法适用于计算从起点到地图中所有节点的距离。如果你只需要到一个点的距离，A算法更快。它基本上是相同的算法，只是A不会扩展不需要的节点。无论是Dijkstra还是A都可以使用斐波那契堆（如果你关心性能），并且在代码中看起来非常相似。当然，你需要一个启发式算法来实现A。如果没有启发式算法，那么Dijkstra算法确实非常好。 - phoenix7360

我没有提到启发式方法，因为它对于这样一个小问题并不相关。如果我们正在考虑如何从纽约开车到加利福尼亚，Dijkstra算法是一个糟糕的选择，这是显而易见的原因，但在这种情况下，“在这里使用Dijkstra算法没有任何理由。” - SplinterReality

是的，我明白了。对于这个特定的小案例来说，这并不重要。我不确定问题是否只针对这个具体示例，还是更一般的讨论。 - phoenix7360

Answer 1

就像SplinterReality所说的:在这里使用Dijkstra算法没有理由不用。

下面的代码是我从这里借鉴并修改以解决问题中的示例。

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Vertex implements Comparable<Vertex>
{
    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<Vertex> vertexQueue = new PriorityQueue<Vertex>();
        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<Vertex> getShortestPathTo(Vertex target)
    {
        List<Vertex> path = new ArrayList<Vertex>();
        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<Vertex> path = getShortestPathTo(Z);
        System.out.println("Path: " + path);
    }
}

上述代码生成：

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

- luke

---

@luke 有没有建议可以找到多个节点之间的最佳路径？该代码返回每个路径首先计算出的相同路径。A --> Z 到Z的距离：49.0 路径：[A，M，R，P，Z]B --> Z 到Z的距离：49.0 路径：[A，M，R，P，Z]两者结果相同？我不确定为什么。你能帮忙检查一下吗？ - Anoop Chandrika HarisudhanNair

应该将 "vertexQueue.remove(v);" 修改为 "vertexQueue.remove(u);"。 - yalkris

避免使用这个。虽然它工作速度快，但修改起来很麻烦。请参考一些好的资料：http://www.vogella.com/tutorials/JavaAlgorithmsDijkstra/article.html - N3sh

你的例子是不正确的，我的意思是除了 AMRPZ 之外没有其他可行的从 A 到 Z 的方式，我尝试了你的解决方案，但在一个更加复杂的图形上不能正常工作。 - henok

就像 @N3sh 2.5 年前所说的一样。Vogella的文章是最好的。当你试图修改这个代码库时，你会学到很多东西。 - Ercan Akkök

Answer 2

估计sanjan:

Dijkstra算法的思想是按顺序探索图中的所有节点。该算法存储一个优先队列，其中节点根据从起点到该节点的成本排序，每次算法迭代执行以下操作：

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

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

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

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

// Create a simple weighted directed graph with Hipster where
// vertices are Strings and edge values are just doubles
HipsterDirectedGraph<String,Double> 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"));

您只需要用自己的图形定义替换原来的定义，然后按照示例实例化算法即可。

希望这有所帮助！

- Adrián González

Answer 3

维护一个节点列表，按距离从起始节点排序。一开始，只有起始节点在列表中。

在你到达目的地之前：访问距离起始节点最近的节点，这将是你排序列表中的第一个节点。当你访问一个节点时，将其所有相邻的未访问过的节点添加到列表中。重复此过程！

- Akinakes

Answer 4

这可能有些晚了，但是没有人提供清晰的算法工作原理的解释。

Dijkstra的思想很简单，以下是伪代码。Dijkstra将所有节点分为两个不同的集合：未确定和已确定。最初，所有节点都在未确定的集合中，即它们仍需评估。

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

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

如果使用所选边可以缩短从源到此节点的已知距离，则更新距离并将该节点添加到需要评估的节点中。

请注意，Dijkstra还确定了每个节点在其到源的路径上的前继节点。我省略了伪代码以简化它。

感谢Lars Vogel提供的帮助

- user3829791

Answer 5

您可以查看一个完整的示例，使用Java 8、递归和流 -> Java实现Dijkstra算法

- Jesus Dana