Je travaillais sur un programme qui imprime la distance et le chemin. J'ai bien la distance qui fonctionne bien, mais le problème que j'ai vint lorsque j'essaie d'imprimer le chemin. J'ai essayé un tas de choses qui ont abouti à des défauts de segmentation ou à imprimer simplement max_int. En ce moment, il suffit d'imprimer les nœuds avec le poids le plus court en arrière, peu importe si le nœud est dans le chemin ou non.
Voici le code et ci-joint sera un graphique, et veuillez noter que je vais modifier cela à Prenez la saisie de l'utilisateur pour la source et la destination, mais pour moi, il suffit de tester le code que je viens de faire la source 0 et de la destination 4. Aussi ci-joint est une photo du graphique.
graphique
3 Réponses :
En regardant le code, je suis à peu près sûr que le problème principal est que vous n'ayez pas réellement implémenter l'algorithme de Dijkstra.
En particulier, vous n'avez pas besoin de travailler à travers tous les nœuds (ce que vous faites actuellement). Au lieu de cela, à partir du début, vous suivez le chemin le plus court possible jusqu'à atteindre la destination.
Au début, vous mettez exactement un nœud dans votre Minheap: le nœud de départ avec la distance 0.
Votre boucle doit prendre l'élément supérieur du tas, vérifier s'il s'agit de la destination. Si oui, cassez. Sinon, mettez tous tous les voisins non visionnés avec leur distance respective (distance du nœud actuel + poids de bord) dans le tas min.
Au cours de cette traversée, il est logique de stocker le nœud que vous venez de chaque nœud visité. Cela vous permet de traverser le chemin de retour, une fois que vous atteignez la destination.
Cela étant dit: j'ai aussi des doutes sur votre tas min. Je ne suis pas sûr de ce que vous faites là-bas, mais une fois que l'utilisateur du Min Heap commence à accéder aux éléments par index, la conception est très cassée.
Sa ne pas imprimer le chemin. Il s'agit simplement d'imprimer tous les nœuds même s'ils sont sur le chemin ou non.
Réponse remplacée.
code pseudo pour imprimer le chemin à l'envers: Il est basé sur l'observation que le bord pour lequel dist + edge_weight est minimum est sur le chemin (lorsque vous regardez en arrière).
Je veux imprimer le chemin afin que ce soit un ordre correct. Je comprends le pseudocode que j'ai juste besoin de savoir comment le mettre en œuvre avec ce code.
Si vous souhaitez commander correctement les nœuds de magasin sur la liste et imprimez-le en arrière.
Est-ce votre code? J'ai déduit que vous pourrez l'écrire vous-même, je vous ai pu écrire ce code. Désolé, je n'écrirai pas tout le code pour vous :(
Le problème que j'avais n'était pas bien expliqué par moi. Ce qui se passait était qu'il immettait tous les nœuds non seulement quelques-uns. Je n'ai pas besoin de vous pour écrire le code que je voulais juste savoir pourquoi il n'était pas d'impression de chemins correctement
Dans l'algorithme de Dijkstra, vous ajoutez de nouveaux nœuds (la jambe la plus courte) à l'ensemble de nœud déjà visité jusqu'à ce que vous incluiez la destination. Supposons que vous incluons un champ Ce pointeur est très utile, comme pour chaque nœud visité, il stocke la route vers l'origine sur le chemin le plus court, non seulement pour le nœud que vous êtes intéressé. IN. Je n'ai pas vérifié votre implémentation, comme vous l'avez dit que votre problème ne trouvait que la route de la destination, donc je n'inclut pas votre code patché . Je te laisse juste ça, comme un exercice. J'essaie uniquement de vous donner un indice , de ne pas résoudre vos devoirs. Mes excuses pour cela. J'ai écrit une mise en œuvre complète de l'algorithme. Cela sera probablement bien traduit en C ++, comme vous l'avez noté dans vos commentaires, vous devez en avoir besoin. Il est composé de trois fichiers, prev (un pointeur sur un nœud) dans le struct adjlistnode , tant que vous incluez les nœuds dans l'ensemble des nœuds déjà accessibles, vous faites. Ce pointeur doit indiquer au nœud qu'il a été attaché, lorsque vous avez ajouté le nœud au jeu de nœuds accessibles. Tant que le nœud qu'il est attaché ait été ajouté, il aura son noeud prev pointant sur le nœud qu'il a été attaché à ... et ainsi de suite. Le premier nœud (le nœud de départ) fait simplement des points de nulle part (il est null , car il n'a jamais été marqué - c'était déjà dans l'ensemble lorsque vous avez commencé), vous avez donc le chemin inverse de Le nœud d'origine, en suivant les pointeurs prev à partir de chaque nœud visité à l'origine. Vous pouvez écrire un sous-programme comme celui-ci: NOTE
2e note
main.c (programme principal), dijkstra.h (en-tête avec les définitions de structure) et dijkstra.c ( Mise en œuvre) Il est disponible ici .
Je l'ai compris il y a longtemps haha. J'aurais même dû demander à cela mon problème était une erreur muette.
Sûr de C ++? Ressemble plus à c (du moins pour moi).
Il n'y a pas de "C / C ++". Veuillez lire les descriptions des balises que vous avez appliquées. En outre, en tant que nouvel utilisateur ici, prenez le tour et lisez Comment demander .
Je viens de le résoudre, désolé pour ça. Ceci est en C mais je vais utiliser ultérieurement des en-têtes et d'autres choses en C ++ avec ce code. Mais pour la réponse actuelle en c.
@Robjames, vous avez fait de mauvaises modifications (ou effacer) votre question, car elle ne sera pas rentable pour personne après cela. Vous feriez mieux de le laisser tel qu'il était, au lieu d'effacer son contenu, il peut donc être d'aide à n'importe qui plus tard. Une fois que le problème est résolu, cela ne vous intéresse probablement pas, mais les gens recherchent ici les réponses avant de poser leurs questions.