Java - Trouver le plus court chemin entre 2 points sur une carte pondérée de distance

J'ai besoin d'un algorithme pour trouver le chemin le plus court entre deux points sur une carte
route de la distance est indiquée par un numéro.

ce qui est donné:
Ville De Départ Un
La Ville De Destination, Z

Liste de Distances entre les Villes:

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

Je pensais que je pouvais utiliser l'algorithme de Dijkstra , cependant il trouve la distance la plus courte vers toutes les destinations. pas seulement un.

Toute suggestion est apprécié.

source d'informationauteur sanjan

  1. 5

    Estimé sanjan:

    L'idée de l'Algorithme de Dijkstra est d'explorer tous les nœuds du graphe d'une façon ordonnée. L'algorithme stocke une file d'attente de priorité où les nœuds sont commandés en fonction du coût de la démarrer, et à chaque itération de l'algorithme, les opérations suivantes sont effectuées:

    1. Extrait de la file d'attente du nœud avec le coût le plus bas depuis le début, N
    2. Obtenir ses voisins (N') et leurs coûts associés, qui est le coût(N) + coût(N, N, N')
    3. Insérer dans la file d'attente des nœuds voisins N', avec la priorité donnée par leur coût

    Il est vrai que l'algorithme calcule le coût du trajet entre le début (dans votre cas) et tout le reste des nœuds, mais vous pouvez arrêter l'exploration de l'algorithme lorsqu'il atteint l'objectif (Z dans votre exemple). À ce point, vous savez que le coût compris entre A et Z, et le chemin les reliant.

    Je vous recommande d'utiliser une bibliothèque qui implémente cet algorithme au lieu de coder votre propre. En Java, vous pouvez prendre un coup d'oeil à la Hipster bibliothèquequi a un très conviviale pour générer le graphique et commencer à utiliser les algorithmes de recherche.

    Ici vous avez un exemple de la façon de définir le graphique et commencer à utiliser Dijstra avec 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"));

    Vous n'avez qu'à remplacer la définition de la partie graphique pour votre propre, puis instancier l'algorithme comme dans l'exemple.

    J'espère que cela aide!

  2. 3

    Ce peut-être trop tard, mais Pas fourni une explication claire du fonctionnement de l'algorithme

    L'idée de Dijkstra est simple, laissez-moi vous montrer ce avec le pseudo-code suivant.

    Dijkstra, les partitions de tous les nœuds en deux ensembles distincts. Instable et se sont installés. Initialement, tous les nœuds sont dans l'incertain, par exemple, ils doivent encore être évalués.

    Au premier abord que le nœud source est mis dans le jeu de settledNodes. Un nœud spécifique sera déplacé à l'réglé réglé que si le plus court chemin de la source à un nœud particulier n'a été trouvé.

    L'algorithme s'exécute jusqu'à ce que le unsettledNodes ensemble est vide. À chaque itération, il sélectionne le nœud ayant la plus faible distance à la source nœud de la unsettledNodes ensemble. E. g. Il lit tous les bords, qui sont en sortant de la source et évalue chaque nœud de destination à partir de ces bords, qui ne sont pas encore réglés.

    Si la distance connue à partir de la source de ce nœud peut être réduite lorsque l'arête sélectionnée est utilisé, la distance est mise à jour et le nœud est ajouté pour les nœuds qui doivent évaluation.

    Veuillez noter que Dijkstra détermine également le pré-successeur de chaque nœud sur son chemin vers la source. J'ai laissé ça de la pseudo-code pour la simplifier.

    Crédits à Lars Vogel

  3. 1

    Maintenir une liste de nœuds, vous pouvez voyager à, triées par ordre de distance à partir de votre nœud de départ. Au début seulement votre nœud de départ sera dans la liste.

    Alors que vous n'avez pas atteint votre destination: Visite du nœud le plus proche du nœud de départ, ce sera le premier nœud dans votre liste triée. Lorsque vous visitez un nœud, ajouter l'ensemble de ses nœuds voisins à votre liste à l'exception de ceux que vous avez déjà visités. Répétez!