Java - Znajdź najkrótszą ścieżkę między 2 punktami na mapie ważonej na odległość

Question

Potrzebuję algorytmu, aby znaleźć najkrótszą ścieżkę między dwoma punktami na mapie , gdzie droga jest oznaczona numerem.

co jest podane: Początek miastu Destination Miasto Z

Lista Odległości między miastami:

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

Pomyślałem, że mogę użyć algorytmu Dijkstry, ale znajdzie najkrótszy dystans do wszystkich miejsc docelowych. nie tylko jeden.

Wszelkie sugestie są mile widziane.

Answer 1

Jak SplinterReality powiedział: There's no reason not to use Dijkstra's algorithm here.

Kod Poniżej ponacinane z here i modyfikować go rozwiązać przykład w pytaniu.

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); 
    } 
} 

Powyższy kod tworzy:

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

Answer 2

Utrzymanie listy węzłów, do których można podróżować, posortowane według odległości od węzła początkowego. Na początku tylko twój węzeł początkowy będzie na liście.

Podczas gdy nie dotarłeś do celu: Odwiedź węzeł najbliższy węzłowi startowemu, będzie to pierwszy węzeł na posortowanej liście. Podczas odwiedzania węzła dodaj wszystkie sąsiednie węzły do ​​listy, z wyjątkiem tych, które już odwiedziłeś. Powtarzać!

Answer 3

To może zbyt późno, ale Nikt nie zapewniono jasne wyjaśnienie, jak działa algorytm

Pomysł Dijkstra jest proste, niech mnie pokaż to za pomocą następującego pseudokodu.

Dijkstra dzieli wszystkie węzły na dwa odrębne zestawy. Nierozliczone i rozliczone. Początkowo wszystkie węzły znajdują się w zbiorze nierozliczonym, np. muszą one być nadal oceniane.

Najpierw tylko węzeł źródłowy jest umieszczany w zbiorze Utrwalonych węzłów. Określony węzeł zostanie przeniesiony do ustalonego zestawu, jeśli zostanie znaleziona najkrótsza ścieżka ze źródła do określonego węzła.

Algorytm działa, dopóki nierozstrzygnięty zbiór Nodes nie jest pusty. W każdej iteracji wybiera węzeł o najniższej odległości do węzła źródłowego z nierozliczonego zestawu Nodes. Na przykład. Odczytuje wszystkie krawędzie wychodzące ze źródła i ocenia każdy węzeł docelowy z tych krawędzi, które jeszcze nie zostały ustalone.

Jeśli znana odległość od źródła do tego węzła może zostać zmniejszona, gdy używana jest wybrana krawędź, odległość jest aktualizowana, a węzeł jest dodawany do węzłów wymagających oceny.

Należy pamiętać, że Dijkstra określa także pre-następcę każdego węzła w drodze do źródła. Zostawiłem to z pseudo kodu, aby go uprościć.

kuponów do Lars Vogel

Answer 4

Szacunkowa sanjan:

Ideą Algorytm Dijkstry jest zbadać wszystkie węzły grafu w uporządkowany sposób. Algorytm przechowuje kolejkę priorytetową węzły są uporządkowane zgodnie z kosztem od początku i w każdej iteracji algorytmu poniższe operacje:

1. ekstrakt z kolejki węzeł o najniższym kosztach z start, N
2. Uzyskaj sąsiadów (N ') i związane z nimi koszty, które są kosztem (N) + koszt (N, N')
3. Wstawiaj w kolejce sąsiednie węzły N ', z priorytetem nadanym przez ich koszt

To prawda, że ​​algorytm oblicza koszt p ath pomiędzy początkiem (A w twoim przypadku) a wszystkimi pozostałymi węzłami, ale możesz zatrzymać eksplorację algorytmu, gdy osiągnie cel (Z w twoim przykładzie). W tym momencie znasz koszt między A i Z i ścieżkę, która je łączy.

Polecam użyć biblioteki, która implementuje ten algorytm zamiast kodowania własnego. W Javie możesz rzucić okiem na Hipster library, który ma bardzo przyjazny sposób generowania wykresu i rozpoczęcia korzystania z algorytmów wyszukiwania.

Tutaj masz przykład jak zdefiniować wykres i zacząć używać Dijstra z 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")); 

Wystarczy tylko podstawić definicję wykresu, a następnie utworzyć instancję algorytmu, jak w przykładzie.

Mam nadzieję, że to pomoże!