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

Question

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

что дано: Start Город А Направление Город Z

Список расстояния между городами:

A - B: 10
F - K: 23
R - M: 8
K - O: 40
Z - Р: 18
J - K: 25
Д - Б: 11
М - А: 8
P - R: 15

Я думал, что могу использовать алгоритм Дейкстры, однако он находит кратчайшее расстояние до всех пунктов назначения. не только один.

Любое предложение приветствуется.

Answer 1

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

Код ниже I порезал от 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] 

Answer 2

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

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

Answer 3

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

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

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

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

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

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

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

Кредиты Lars Vogel

Answer 4

Оценочное sanjan:

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

1. Извлечение из очереди узел с наименьшей стоимостью от start, N
2. Получить его соседние (N ') и связанные с ними затраты, которые являются стоимостью (N) + стоимостью (N, N')
3. Вставить в очередь соседние узлы N ', с приоритетом, заданным их стоимость

Это правда, что алгоритм вычисляет стоимость p между стартом (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")); 

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

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