L'algorithme de Dijkstra en Java pour la matrice avec des obstacles

Question

J'essaye d'implémenter l'algorithme de Dijkstra afin de trouver le chemin le plus court entre 2 points dans une grille (x, y) mais le problème est que je ne peux que monter, descendre, droite et gauche.

J'ai une ArrayList contenant les x et ys des points que je dois transmettre et une autre ArrayList des points qui sont des obstacles sur la grille, j'essaye d'écrire une fonction qui retourne une ArrayList du mouvement nécessaire afin de finir tout le chemin.

Dans l'exemple: 1,1,1,2,3,4,1 .. 1 étant à droite 2 étant à gauche et 3 étant en haut et finalement 4 étant en bas.

Pouvez-vous s'il vous plaît me fournir quelques conseils et/ou exemples.

Answer 1

Tout d'abord, sachez que l'algorithme de Dijkstra est traditionnellement utilisé pour les graphiques pondérés. Il pourrait toujours fonctionner avec les bords de l'unité (tous les poids 1), mais ce n'est peut-être pas votre solution la plus efficace. De toute façon, quel que soit l'algorithme que vous utilisez, vous devrez traiter votre grille comme un graphique. Pour ce faire, créez un ensemble d'arêtes. S'il n'y a pas de restrictions au-delà de "pas de diagonales" alors vos bords seront la connexion entre chaque point et ses voisins au-dessus, en dessous et à côté de lui. Vous pouvez ensuite opérer sur le graphique en itérant sur les bords et les points du graphique.