L'algorithme de Dijkstra avec un tableau 2d

Question

Ces derniers jours, j'ai essayé d'implémenter cet algorithme. Jusqu'à présent, j'ai réussi à faire un tableau 2D dynamique et insérer les distances entre les nœuds, une fonction pour supprimer un chemin entre les nœuds et une fonction qui me dit s'il y a un chemin entre deux nœuds. Maintenant je voudrais implémenter une fonction qui retourne le chemin le plus court du noeud A au noeud B. Je sais comment fonctionne l'algorithme de dijkstras et j'ai lu le pseudo code sur le wiki sans pouvoir écrire du code moi-même. Je suis vraiment coincé ici.

J'ai réfléchi à la façon dont le code devrait ressembler et ce qui devrait arriver c'est pourquoi j'ai fait cette fonction qui me dit s'il y a un chemin entre deux nœuds. Ai-je besoin d'autres fonctions d'aide qui faciliteraient la mise en œuvre des dijkstras? Pour l'instant je n'ai que 3 nœuds mais le code que je voudrais écrire doit fonctionner en général pour n nœuds.

Toute sorte d'aide est appréciée.

Answer 1

Vous y pensez probablement beaucoup.

Vous avez besoin de 2 choses. Une structure graphique propre que vous comprenez. Une bonne description de l'algorithme que vous comprenez. Si vous avez les deux. Commencez simplement à écrire du code. Les assistants nécessaires deviendront évidents sur le chemin.

- modifier -
Vous aurez probablement besoin d'une des structures de données suivantes
std::vector std::list std::priority_queue

Answer 2

J'ai trouvé plusieurs codes pour cet algorithme, mais peut-être est-ce mieux le plus simple pour mieux le comprendre, donc vous pouvez vérifier les différences entre le vôtre et celui-ci, et compléter le vôtre. Il est toujours préférable de programmer votre chemin. Jetez un oeil à celui-ci et voir si cela aide.

http://vinodcse.wordpress.com/2006/05/19/code-for-dijkstras-algorithm-in-c-2/

Bonne chance.

Answer 3

Modifier: Code supprimé, et je vais donner des conseils:

1. graphique de magasin liste des listes de contiguïté de chaque sommet. (quelque chose comme ceci vector < vector < pair<int,int> > > g (n);)
2. Utilisez une structure de données pour garder la trace de ce qui est le sommet avec une distance minimale dans l'état actuel. (peut-être définir, ou priority_queue pour avoir O(m log(n)) complexité)
3. Chaque fois que vous prenez le sommet high_priority (sommet avec une distance actuelle minimale), supprimez-le de votre structure_données et mettez à jour les distances adjacentes aux sommets supprimés.

---

Note: Si vous voulez obtenir le chemin minimal aussi bien, puis garder un peu vector<int> previous et chaque fois que la distance mise à jour du sommet (par exemple v) mis previous[v] = index of vertex from where you came here. Votre chemin est last, prev[last], prev[prev[last]],...,first dans l'ordre inverse.