Java - найдите кратчайший путь между двумя точками на карте с расстоянием

Ответ 1

Как сказал SplinterReality: There no reason not to use Dijkstra algorithm here.

Приведенный ниже код я добавил из здесь и изменил его, чтобы решить пример в вопросе.

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]

Ответ 2

Предполагаемый санджан:

Идея алгоритма Дейкстры состоит в том, чтобы исследовать все узлы графика упорядоченным образом. Алгоритм хранит приоритетную очередь, где узлы упорядочиваются в соответствии с затратами с самого начала, и на каждой итерации алгоритма выполняются следующие операции:

• Извлеките из очереди node с самой низкой стоимостью с самого начала, N
• Получите своих соседей (N ') и их соответствующую стоимость, стоимость (N) + стоимость (N, N')
• Вставить в очередь соседние узлы N ', причем приоритет указан их стоимостью

Верно, что алгоритм вычисляет стоимость пути между началом (A в вашем случае) и всеми остальными узлами, но вы можете остановить исследование алгоритма, когда он достигнет цели (Z в вашем примере). На этом этапе вы знаете стоимость между A и Z и путь, соединяющий их.

Я рекомендую вам использовать библиотеку, которая реализует этот алгоритм вместо того, чтобы кодировать ваши собственные. В Java вы можете взглянуть на Hipster library, которая имеет очень удобный способ генерации графика и начала использования алгоритмов поиска.

Здесь у вас есть пример того, как определить график и начать использовать Dijstra с Hipster.

// 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"));

Вам нужно только подставить определение графика для своего, а затем создать экземпляр алгоритма, как в примере.

Надеюсь, это поможет!

Ответ 3

Возможно, это слишком поздно, но Никто не дал ясного объяснения того, как работает алгоритм

Идея Дийкстры проста, позвольте мне показать это со следующим псевдокодом.

Dijkstra разбивает все узлы на два разных множества. Неустроенный и устоявшийся. Первоначально все узлы находятся в неустановленном наборе, например. они должны быть все еще оценены.

Сначала только набор node помещается в набор settNodes. Конкретный node будет перемещен в установленный набор, если найден самый короткий путь от источника к определенному node.

Алгоритм выполняется до тех пор, пока набор unsettledNodes не будет пустым. На каждой итерации выбирается node с наименьшим расстоянием до источника node из набора unsettledNodes. Например. Он считывает все ребра, исходящие из источника, и оценивает каждый пункт назначения node из этих ребер, которые еще не установлены.

Если известное расстояние от источника до этого node может быть уменьшено при использовании выбранного края, расстояние обновляется, а node добавляется к узлам, которые нуждаются в оценке.

Обратите внимание, что Dijkstra также определяет пре-преемника каждого node по пути к источнику. Я оставил это из псевдокода, чтобы упростить его.

Кредиты Ларс Фогель

Ответ 4

Поддерживайте список узлов, к которым вы можете перемещаться, отсортированные по расстоянию от вашего запуска node. Вначале в списке будет только ваш старт node.

Пока вы не достигли цели: Посетите node, ближайший к началу node, это будет первый node в вашем отсортированном списке. Когда вы посещаете node, добавьте все свои соседние узлы в свой список, кроме тех, которые вы уже посетили. Повторите!

Ответ 5

Вы можете увидеть полный пример с использованием Java 8, рекурсии и потоков → алгоритм Дейкстры с Java