J'ai mon graphe implémenté avec des listes chaînées, pour les sommets et les arêtes, et cela devient un problème pour l'algorithme de Dijkstra. Comme je l'ai dit sur une question précédente, je convertis this code qui utilise une matrice d'adjacence pour travailler avec mon implémentation graphique.Gros problème avec l'algorithme de Dijkstra dans une implémentation de graphe de liste chaînée
Le problème est que lorsque je trouve la valeur minimale, j'obtiens un index de tableau. Cet index aurait une correspondance avec l'index de vertex si les sommets de graphe étaient stockés dans un tableau à la place. Et l'accès au sommet serait constant.
Je n'ai pas le temps de changer d'implémentation graphique, mais j'ai une table de hachage, indexée par un nombre unique (mais qui ne commence pas à 0, c'est comme 100090000) qui est le problème ayant. Chaque fois que j'en ai besoin, j'utilise l'opérateur modulo pour obtenir un nombre compris entre 0 et le nombre total de sommets. Cela fonctionne très bien quand j'ai besoin d'un index de tableau à partir du nombre, mais quand j'ai besoin du numéro de l'index de tableau (pour accéder au sommet de distance minimum calculé en temps constant), pas tellement.
J'ai essayé de chercher comment inverser l'opération modulo, comme, 100090000 mod 18000 = 10000 et, 10000 invmod 18000 = 100090000 mais n'a pas pu trouver un moyen de le faire. Ma prochaine alternative est de construire une sorte de tableau de référence où, dans l'exemple ci-dessus, arr [10000] = 100090000. Cela réglerait le problème, mais il faudrait boucler le graphique entier une fois de plus. Est-ce que j'ai une solution meilleure/plus facile avec ma mise en œuvre graphique actuelle?
De quelle langue s'agit-il? Et comment est construite la liste chaînée? – Kyte
Désolé, C, tag ajouté. Que voulez-vous dire comment est-il construit? C'est une liste chaînée, avec un pointeur vers le prochain nœud ... –