Implémentation de l'algorithme de Dijkstra

J'écris donc une implémentation JavaScript de l'algorithme de Dijkstra.Implémentation de l'algorithme de Dijkstra

J'ai lu beaucoup de Wikipedia page, ce qui m'a aidé à traduire les étapes en code. J'ai également lu this Stack Overflow question, ce qui fait partie de ma question.

De A, le seul chemin est B, cela nous donne

O => AB = 12;

O => C = 7

C est maintenant le plus faible distance et est le nouveau noeud courant

O => CD = 8

Puisque D est la destination et 8 < 12, la itinéraire CD est choisi.

Comment implémentez-vous cette décision dans le code? À l'heure actuelle, mon script base le nœud à choisir parmi ceux qui sont adjacents à l'actuel, est-ce que chaque décision doit être exécutée à travers ce nouveau type d'évaluation? Par ailleurs, here est mon code (désordonné).

Source

2012-10-29 Polyov

Votre code semble un peu brouillon car vous n'avez pas utilisé de variables locales pour 'currentEdge' et' currentNeighbor'. En outre, vous devez d'abord savoir lequel ('c1' ou 'c2') est le noeud voisin et ensuite appliquer la condition dessus au lieu de répéter cette if-instruction. Je n'ai pas regardé plus bas ... – Bergi

mes bases de script ce nœud à choisir sur ceux qui sont adjacents au courant un

Non Votre liste connectedNodes (trié par la distance) devrait être globale, non seulement pour le noeud courant. Puis, pour le premier nœud (le moins éloigné), ajoutez tous les voisins non visités à la liste, toujours triés par distance. Marquez le noeud actuel visité et continuez avec le prochain noeud non visité le moins éloigné.

Source

2012-10-29 01:37:59 Bergi

Maintenant, la fonction crache un tableau de 13 espaces avec des nœuds aléatoires: [PasteBin] (http://pastebin.com/CAuBEmzv) – Polyov

Merci de m'avoir aidé à nettoyer mon code et d'en faire plus sens, mais cette réponse ne répond toujours pas à ma question de savoir comment mettre en œuvre la décision. Il n'y a pas d'indicateur clair dans mon script qu'il y avait un certain chemin correct ou le plus court, juste à quels nœuds l'algorithme regardait, et ensuite quelle était la distance finale. – Polyov

Pour obtenir le chemin trouvé, vous devez enregistrer le prédécesseur pour chaque nœud que vous ajoutez à la liste. Ensuite, vous pouvez revenir à cette route du nœud de fin au nœud de départ. – Bergi

Implémentation de l'algorithme de Dijkstra

Répondre

Questions connexes