Algorithme de Dijkstra C ++

L'algorithme de Dijkstra est également connu comme l'algorithme de chemin le plus court possible. Il s'agit de la procédure pour trouver le chemin le plus court entre les nœuds / bords du graphique. Le graphique le plus court d'une arbre est créé en commençant du sommet source à tous les autres points du graphique.

Algorithme

• Avant la mise en œuvre directe du graphique Dijkstra dans le langage de programmation C ++, nous devons comprendre le fonctionnement de cet algorithme graphique.
• La première étape est la création de «SPTSet», qui est abrégée comme l'ensemble d'arborescence de chemin le plus court; Il stocke l'enregistrement des sommets qui sont inclus dans le chemin le plus court. Au stade initial, cet ensemble est déclaré nul.
• Dans l'étape suivante, tout d'abord, toutes ces valeurs aux nœuds sont déclarées infinies, car nous ne connaissons pas le poids des chemins jusqu'à présent.
• Choisissez un sommet «u» qui n'est pas déjà présent dans SPTSET et qui a une valeur minimale. Puis incluez-le à SPTSET. Après cela, mettez à jour les valeurs de distance de tous ces nœuds qui sont des sommets adjacents de «U."Tout cela se fait sous la boucle jusqu'à ce que SPTSet puisse contenir tous les sommets.

Implémentation de l'algorithme graphique de Dijkstra

Voici la mise en œuvre du graphique Dijkstra, où un programme est écrit pour la représentation de la matrice d'adjacence de ce graphique. Démarrez le programme en ajoutant deux bibliothèques très essentielles pour l'accomplissement du programme dans le langage de programmation C ++ qui nous permet d'utiliser des fonctionnalités CIN et COUT.

#inclure
#inclure

Après avoir décrit les bibliothèques, nous allons maintenant fournir la taille ou les sommets du graphique dans lequel nous avons besoin du chemin le plus court. Nous avons donné 9 sommets, ce qui signifie que la matrice est un carré de [9] [9].

#define v 9

«V» est pour les sommets. Comme l'algorithme nécessite de nombreuses étapes pour accomplir la tâche fournie, chaque étape ou processus est divisé en fonctions distinctes pour les exécuter afin que le code soit clair et qu'il n'y a pas d'ambiguïté concernant la logique. De plus, la complexité est également supprimée.

La fonction est créée ici pour rechercher le sommet qui a une valeur de distance minimale; Il contient l'ensemble des sommets qui ne sont pas inclus dans l'arbre ayant le chemin le plus court. La fonction contiendra le tableau de distance et un SPTET de type bool, l'ensemble d'arborescence de chemin le plus court et le tableau comme paramètre de la fonction. À l'intérieur de la fonction, la valeur minimale est initialisée en déclarant une variable de type entier qui stockera la valeur renvoyée. Deux variables, Max et le min_index sont introduites.

Int min = int_max, min_index;

Une boucle pour une boucle est utilisée ici; dans lequel un sommet de départ dans tous les sommets est pris, la boucle se poursuivra jusqu'à ce que tous les sommets soient traversés. Une condition est appliquée ici en utilisant une instruction IF qui vérifie si l'ensemble de chemin le plus court est faux moyen, il est vide en ce moment, et la distance du sommet est plus petite que celle de la valeur minimale du sommet, qui est déclaré plus tôt, puis attribuer la valeur actuelle du sommet comme min, et le min_index contiendra également la même valeur du sommet.

Min = dist [v], min_index = v;

Une fois la valeur minimale du sommet du sommet, le processus de création d'une fonction qui affichera le tableau de distance qui a été construit plus tôt. Une boucle iratera chaque index qui sera accessible et affiché. Tout d'abord, le numéro de sommet s'affiche à partir de la valeur zéro, et la distance du sommet de la source est également mentionnée ici avec une séquence. Cette fonction est déclarée ici, mais elle sera appelée plus tard dans le programme lorsque tout le chemin est calculé comme la distance la plus courte.

La partie principale de l'ensemble du code source est déclarée maintenant, où la mise en œuvre du chemin le plus court à source unique est calculée. Un graphique sera représenté par la représentation de la matrice d'adjacence. Cette fonction prendra une matrice de graphe et la source comme valeurs de paramètre qui agiront comme entrée pour le calcul de la distance. Tout d'abord, à l'intérieur de la fonction, nous déclarerons le tableau de sortie qui contiendra le chemin le plus court de la source à un point spécifique. Deuxièmement, un tableau de variable booléen est déclaré, qui reviendra vrai si le sommet est inclus dans la détermination du chemin le plus court au début.

Int dist [v]; bool sptset [v];

Toutes les distances seront définies comme infinies, et le tableau de chemin d'arbre le plus court est faux. À l'aide d'une boucle, tout ce processus aura lieu.

À l'intérieur de la boucle, le sommet de distance minimum est choisi dans l'ensemble des sommets qui ne sont pas encore traités. Dans la première itération, «u» est toujours égal au sommet source.

Int u = MindIstance (dist, SPTSet);

Les sommets choisis et traversés sont choisis et marqués comme traités en définissant la variable booléenne est vraie.

SPTSet [u] = true;

Lorsqu'un sommet est ajouté, tous les sommets adjacents à ce sommet particulier sont également vérifiés; Cela a besoin d'une mise à jour. Nous allons donc mettre à jour la valeur de «dist» des sommets adjacents des sommets qui ont été le piquet jusqu'à présent.

À l'intérieur pour Loop, nous mettrons à jour Dist [V] Si et seulement s'il n'est pas dans le SPTSet, il y a une ligne appelée Edge du sommet U à V, et le poids total du chemin qui commence à partir de «SRC» «V» en passant par «u» est plus petit que la valeur actuelle présente dans la dist [v].

Dist [v] = dist [u] + graphique [u] [v];

Après cela, la fonction d'impression que nous avons déclarée ci-dessus est appelée en passant le tableau Dist [] en tant que paramètre.

imprimésolution (dist);

Dans le programme principal, nous créons un graphique matriciel 9 * 9. Et puis, l'appel de fonction pour la fonction Dijkstra est fait, à travers lequel le graphique est passé.

Enregistrer l'intégralité du code. Compilez le code en utilisant un compilateur G ++ dans le terminal Ubuntu. '-o' est un symbole qui enregistre la sortie du fichier.

$ g ++ -o dij dij.c
$ ./ dij

Vous pouvez voir que tous les sommets de chaque ligne séparée sont affichés avec la distance de chaque sommet de la source.

Ce code aide à calculer la distance la plus courte, mais elle ne prend pas en charge le calcul des informations sur le chemin. Ce code source est bon pour les graphiques non dirigés mais peut également être possible à utiliser pour les graphiques dirigés. En utilisant ce code, nous pouvons trouver la distance la plus courte du point de source à tous les autres sommets du graphique.

La complexité temporelle du graphique Dijkstra

Nous parlerons de la complexité temporelle de la mise en œuvre. C'est:

0 (v ^ 2).

Cela peut être réduit à 0 (e log v) en utilisant le processus du tas binaire. Le graphique Dijkstra n'est pas pour les graphiques qui ont des poids négatifs.

Conclusion

Cet article contient le processus de recherche de la distance la plus courte entre le nœud source au reste des nœuds. Il peut y avoir de nombreuses approches à ce sujet. Mais le graphique Dijkstra est l'un des meilleurs mécanismes à cet effet. Il est conçu pour les graphiques non dirigés. Nous avons expliqué le processus étape par étape avec le code source pour le rendre vivant pour les nouveaux utilisateurs. Nous espérons que cet effort sera à la hauteur des lecteurs.