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的算法，但是它能找到到所有目的地的最短距离。不仅仅是一个。

如有任何建议，我们将不胜感激。

Answer 1

维护一个可以旅行到的节点列表，按距离起始节点的距离排序。在开始时，列表中只有开始节点。

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

Answer 2

估计sanjan：

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

1. 从队列中提取起始成本最低的节点，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"));

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

我希望这有帮助！

Answer 3

正如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]