ALGORITHME DU PLUS COURT CHEMIN DE DIJKSTRA AVEC EXEMPLES

Le didacticiel suivant nous apprendra l'algorithme du plus court chemin de Dijkstra. Nous comprendrons le fonctionnement de l'algorithme de Dijkstra avec une explication graphique par étapes.

Nous couvrirons les éléments suivants :

Un bref aperçu des concepts fondamentaux du graphique
Comprendre l'utilisation de l'algorithme de Dijkstra
Comprendre le fonctionnement de l'algorithme avec un exemple étape par étape

Alors, commençons.

Une brève introduction aux graphiques

Graphiques sont des structures de données non linéaires représentant les « connexions » entre les éléments. Ces éléments sont connus sous le nom de Sommets , et les lignes ou arcs qui relient deux sommets du graphique sont appelés Bords . Plus formellement, un Graph comprend un ensemble de sommets (V) et un ensemble de bords (E) . Le graphique est noté G(V,E) .

java remplace tout

Composants d'un graphique

Sommets :Les sommets sont les unités de base du graphique utilisées pour représenter des objets, des personnes ou des entités réelles. Parfois, les sommets sont également appelés nœuds.Bords:Les arêtes sont dessinées ou utilisées pour relier deux sommets du graphique. Parfois, les arêtes sont également appelées arcs.

La figure suivante montre une représentation graphique d'un graphique :

Figure 1: Représentation graphique d'un graphique

Dans la figure ci-dessus, les sommets/nœuds sont désignés par des cercles colorés et les arêtes sont désignées par les lignes reliant les nœuds.

Applications des graphiques

Les graphiques sont utilisés pour résoudre de nombreux problèmes réels. Des graphiques sont utilisés pour représenter les réseaux. Ces réseaux peuvent inclure des réseaux téléphoniques ou de circuits ou des chemins dans une ville.

Par exemple, nous pourrions utiliser des graphiques pour concevoir un modèle de réseau de transport dans lequel les sommets affichent les installations qui envoient ou reçoivent les produits, et les arêtes représentent les routes ou les chemins qui les relient. Ce qui suit en est une représentation picturale :

Figure 2: Représentation picturale du réseau de transport

Les graphiques sont également utilisés sur différentes plateformes de médias sociaux comme LinkedIn, Facebook, Twitter, etc. Par exemple, des plateformes comme Facebook utilisent des graphiques pour stocker les données de leurs utilisateurs où chaque personne est indiquée par un sommet, et chacune d'entre elles est une structure contenant des informations telles que l'identifiant de la personne, le nom, le sexe, l'adresse, etc.

Types de graphiques

Les graphiques peuvent être classés en deux types :

Graphique non orienté
Graphique dirigé

Graphique non orienté : Un graphique dont les arêtes n’ont pas de direction est appelé un graphique non orienté. Les arêtes de ce graphique impliquent une relation bidirectionnelle dans laquelle chaque arête peut être parcourue dans les deux sens. La figure suivante affiche un simple graphique non orienté avec quatre nœuds et cinq arêtes.

Figure 3: Un simple graphique non orienté

Graphique dirigé: Un graphique avec des arêtes avec une direction est appelé un graphique orienté. Les arêtes de ce graphe impliquent une relation à sens unique dans laquelle chaque arête ne peut être parcourue que dans une seule direction. La figure suivante affiche un graphique orienté simple avec quatre nœuds et cinq arêtes.

Figure 4 : Un graphique orienté simple

La longueur absolue, la position ou l’orientation des bords dans une illustration graphique n’ont généralement aucune signification. En d’autres termes, nous pouvons visualiser le même graphe de différentes manières en réorganisant les sommets ou en déformant les arêtes si la structure sous-jacente du graphe ne change pas.

Que sont les graphiques pondérés ?

Un graphique est dit pondéré si chaque arête se voit attribuer un « poids ». Le poids d'une arête peut indiquer la distance, le temps ou tout ce qui modélise la « connexion » entre la paire de sommets qu'elle connecte.

Par exemple, nous pouvons observer un nombre bleu à côté de chaque arête dans la figure suivante du graphique pondéré. Ce nombre est utilisé pour indiquer le poids du bord correspondant.

Figure 5 : Un exemple de graphique pondéré

Une introduction à l'algorithme de Dijkstra

Maintenant que nous connaissons quelques concepts de base des graphiques, plongeons-nous dans la compréhension du concept de l'algorithme de Dijkstra.

Vous êtes-vous déjà demandé comment Google Maps trouve l'itinéraire le plus court et le plus rapide entre deux endroits ?

Eh bien, la réponse est L'algorithme de Dijkstra . L'algorithme de Dijkstra est un algorithme graphique qui trouve le chemin le plus court d'un sommet source à tous les autres sommets du graphique (chemin le plus court d'une source unique). Il s'agit d'un type d'algorithme gourmand qui ne fonctionne que sur des graphiques pondérés ayant des poids positifs. La complexité temporelle de l'algorithme de Dijkstra est O(V²) à l’aide de la représentation matricielle d’adjacence du graphique. Cette complexité temporelle peut être réduite à O((V + E)logV) à l'aide d'une représentation de liste de contiguïté du graphique, où DANS est le nombre de sommets et ET est le nombre d'arêtes dans le graphique.

Histoire de l'algorithme de Dijkstra

L'algorithme de Dijkstra a été conçu et publié par Dr. Edsger W. Dijkstra , un informaticien, ingénieur logiciel, programmeur, essayiste scientifique et scientifique des systèmes néerlandais.

Lors d'un entretien avec Philip L. Frana pour les communications de la revue ACM en 2001, le Dr Edsger W. Dijkstra a révélé :

« Quel est le chemin le plus court pour voyager de Rotterdam à Groningue, en général : d'une ville donnée à une ville donnée ? C’est l’algorithme du chemin le plus court, que j’ai conçu en une vingtaine de minutes. Un matin, je faisais du shopping à Amsterdam avec ma jeune fiancée, et fatigués, nous nous sommes assis à la terrasse du café pour boire une tasse de café et je me demandais si je pouvais le faire, et j'ai ensuite conçu l'algorithme du chemin le plus court. . Comme je l'ai dit, c'était une invention de vingt minutes. En fait, il a été publié en 1959, trois ans plus tard. La publication est toujours lisible, elle est en fait plutôt sympa. L’une des raisons pour lesquelles il est si joli est que je l’ai conçu sans crayon ni papier. J'ai appris plus tard que l'un des avantages de concevoir sans crayon ni papier est que vous êtes presque obligé d'éviter toutes les complexités évitables. Finalement, cet algorithme est devenu, à mon grand étonnement, l'une des pierres angulaires de ma renommée.

Dijkstra a réfléchi au problème du chemin le plus court alors qu'il travaillait comme programmeur au Centre mathématique d'Amsterdam en 1956 pour illustrer les capacités d'un nouvel ordinateur connu sous le nom d'ARMAC. Son objectif était de sélectionner à la fois un problème et une solution (produite par l'ordinateur) que les personnes n'ayant aucune formation en informatique pourraient comprendre. Il a développé l'algorithme du chemin le plus court et l'a ensuite exécuté pour ARMAC pour une carte de transport vaguement raccourcie de 64 villes des Pays-Bas (64 villes, donc 6 bits suffiraient pour coder le numéro de la ville). Un an plus tard, il a été confronté à un autre problème de la part des ingénieurs matériels qui exploitaient le prochain ordinateur de l'institut : minimiser la quantité de fil nécessaire pour connecter les broches sur le panneau arrière de la machine. En guise de solution, il a redécouvert l'algorithme appelé algorithme d'arbre couvrant minimal de Prim et l'a publié en 1959.

Fondamentaux de l'algorithme de Dijkstra

Voici les concepts de base de l'algorithme de Dijkstra :

L'algorithme de Dijkstra commence au nœud que nous sélectionnons (le nœud source) et examine le graphique pour trouver le chemin le plus court entre ce nœud et tous les autres nœuds du graphique.
L'algorithme conserve des enregistrements de la distance la plus courte actuellement reconnue entre chaque nœud et le nœud source, et met à jour ces valeurs s'il trouve un chemin plus court.
Une fois que l'algorithme a récupéré le chemin le plus court entre la source et un autre nœud, ce nœud est marqué comme « visité » et inclus dans le chemin.
La procédure se poursuit jusqu'à ce que tous les nœuds du graphique aient été inclus dans le chemin. De cette manière, nous disposons d’un chemin reliant le nœud source à tous les autres nœuds, en suivant le chemin le plus court possible pour atteindre chaque nœud.

Comprendre le fonctionnement de l'algorithme de Dijkstra

UN graphique et sommet source sont des exigences pour l’algorithme de Dijkstra. Cet algorithme est établi sur une approche gourmande et trouve ainsi le choix localement optimal (minima locaux dans ce cas) à chaque étape de l'algorithme.

Chaque sommet de cet algorithme aura deux propriétés définies :

Propriété visitée
Propriété du chemin

Comprenons ces propriétés en bref.

Propriété visitée :

La propriété « visité » indique si le nœud a été visité ou non.
Nous utilisons cette propriété pour ne revisiter aucun nœud.
Un nœud est marqué comme visité uniquement lorsque le chemin le plus court a été trouvé.

Propriété du chemin :

La propriété 'path' stocke la valeur du chemin minimum actuel vers le nœud.
Le chemin minimum actuel implique le chemin le plus court par lequel nous avons atteint ce nœud jusqu'à présent.
Cette propriété est révisée lorsqu'un voisin du nœud est visité.
Cette propriété est importante car elle stockera la réponse finale pour chaque nœud.

Initialement, nous marquons tous les sommets, ou nœuds, non visités car ils n'ont pas encore été visités. Le chemin vers tous les nœuds est également défini sur l'infini en dehors du nœud source. De plus, le chemin vers le nœud source est défini sur zéro (0).

Nous sélectionnons ensuite le nœud source et le marquons comme visité. Après cela, nous accédons à tous les nœuds voisins du nœud source et effectuons une relaxation sur chaque nœud. La relaxation est le processus consistant à réduire le coût pour atteindre un nœud à l’aide d’un autre nœud.

Dans le processus de relaxation, le chemin de chaque nœud est révisé à la valeur minimale parmi le chemin actuel du nœud, la somme du chemin vers le nœud précédent et le chemin du nœud précédent vers le nœud actuel.

Supposons que p[n] soit la valeur du chemin actuel pour le nœud n, p[m] soit la valeur du chemin jusqu'au nœud m précédemment visité, et w soit le poids de l'arête entre le nœud courant et celui visité précédemment (poids du bord compris entre n et m).

Au sens mathématique, la relaxation peut être illustrée par :

p[n] = minimum(p[n], p[m] + w)

Nous marquons ensuite un nœud non visité avec le moins de chemin comme visité à chaque étape suivante et mettons à jour les chemins de son voisin.

Nous répétons cette procédure jusqu'à ce que tous les nœuds du graphique soient marqués comme visités.

Chaque fois que nous ajoutons un nœud à l'ensemble visité, le chemin vers tous ses nœuds voisins change également en conséquence.

Si un nœud reste inaccessible (composant déconnecté), son chemin reste « infini ». Dans le cas où la source elle-même est un composant distinct, alors le chemin vers tous les autres nœuds reste « l'infini ».

Comprendre l'algorithme de Dijkstra avec un exemple

Voici l'étape que nous suivrons pour implémenter l'algorithme de Dijkstra :

Étape 1: Tout d’abord, nous allons marquer le nœud source avec une distance actuelle de 0 et définir le reste des nœuds sur INFINITY.

Étape 2: Nous définirons ensuite le nœud non visité avec la plus petite distance actuelle comme nœud actuel, supposons X.

Étape 3: Pour chaque voisin N du nœud courant X : On ajoutera ensuite la distance actuelle de X avec le poids de l'arête joignant X-N. Si elle est inférieure à la distance actuelle de N, définissez-la comme nouvelle distance actuelle de N.

Étape 4: Nous marquerons ensuite le nœud actuel X comme visité.

Étape 5 : Nous répéterons le processus à partir de 'Étape 2' s'il reste un nœud non visité dans le graphique.

Comprenons maintenant la mise en œuvre de l'algorithme à l'aide d'un exemple :

ajout de chaînes java

Figure 6 : Le graphique donné

Nous utiliserons le graphique ci-dessus comme entrée, avec le nœud UN comme source.
Tout d’abord, nous marquerons tous les nœuds comme non visités.
Nous tracerons la voie à 0 au nœud UN et INFINI pour tous les autres nœuds.
Nous allons maintenant marquer le nœud source UN tel que visité et accéder à ses nœuds voisins.
Note: Nous avons uniquement accédé aux nœuds voisins, pas les avons visités.
Nous allons maintenant mettre à jour le chemin vers le nœud B par 4 avec l'aide de la relaxation car le chemin vers le nœud UN est 0 et le chemin depuis le nœud UN à B est 4 , et le minimum((0 + 4), INFINI) est 4 .
Nous mettrons également à jour le chemin vers le nœud C par 5 avec l'aide de la relaxation car le chemin vers le nœud UN est 0 et le chemin depuis le nœud UN à C est 5 , et le minimum((0 + 5), INFINI) est 5 . Les deux voisins du nœud UN sont maintenant détendus ; nous pouvons donc avancer.
Nous allons maintenant sélectionner le prochain nœud non visité avec le moins de chemin et le visiter. Par conséquent, nous visiterons le nœud B et effectue une relaxation sur ses voisins non visités. Après avoir effectué la relaxation, le chemin vers le nœud C restera 5 , alors que le chemin vers le nœud ET va devenir onze , et le chemin vers le nœud D va devenir 13 .
Nous allons maintenant visiter le nœud ET et effectuer une relaxation sur ses nœuds voisins B, D , et F . Puisque seul le nœud F n'est pas visité, il sera détendu. Ainsi, le chemin vers le nœud B restera tel quel, c'est-à-dire 4 , le chemin vers le nœud D restera également 13 , et le chemin vers le nœud F va devenir 14 (8 + 6) .
Nous allons maintenant visiter le nœud D , et seul le nœud F sera détendu. Cependant, le chemin vers le nœud F restera inchangé, c'est-à-dire 14 .
Puisque seul le nœud F reste, nous le visiterons mais n'effectuerons aucune relaxation car tous ses nœuds voisins sont déjà visités.
Une fois tous les nœuds des graphiques visités, le programme se terminera.

Par conséquent, les chemins finaux que nous avons conclus sont :

 A = 0 B = 4 (A -&gt; B) C = 5 (A -&gt; C) D = 4 + 9 = 13 (A -&gt; B -&gt; D) E = 5 + 3 = 8 (A -&gt; C -&gt; E) F = 5 + 3 + 6 = 14 (A -&gt; C -&gt; E -&gt; F)

Pseudocode pour l'algorithme de Dijkstra

Nous allons maintenant comprendre un pseudocode pour l'algorithme de Dijkstra.

Nous devons conserver un enregistrement de la distance parcourue par chaque nœud. Par conséquent, nous pouvons stocker la distance du trajet de chaque nœud dans un tableau de taille n, où n est le nombre total de nœuds.
De plus, nous souhaitons récupérer le chemin le plus court ainsi que la longueur de ce chemin. Pour surmonter ce problème, nous mapperons chaque nœud au nœud qui a mis à jour en dernier lieu la longueur de son chemin.
Une fois l'algorithme terminé, nous pouvons revenir en arrière du nœud de destination jusqu'au nœud source pour récupérer le chemin.
Nous pouvons utiliser une file d'attente prioritaire minimale pour récupérer de manière efficace le nœud avec la plus petite distance de chemin.

Implémentons maintenant un pseudocode de l'illustration ci-dessus :

Pseudo-code :

 function Dijkstra_Algorithm(Graph, source_node) // iterating through the nodes in Graph and set their distances to INFINITY for each node N in Graph: distance[N] = INFINITY previous[N] = NULL If N != source_node, add N to Priority Queue G // setting the distance of the source node of the Graph to 0 distance[source_node] = 0 // iterating until the Priority Queue G is not empty while G is NOT empty: // selecting a node Q having the least distance and marking it as visited Q = node in G with the least distance[] mark Q visited // iterating through the unvisited neighboring nodes of the node Q and performing relaxation accordingly for each unvisited neighbor node N of Q: temporary_distance = distance[Q] + distance_between(Q, N) // if the temporary distance is less than the given distance of the path to the Node, updating the resultant distance with the minimum value if temporary_distance <distance[n] distance[n] :="temporary_distance" previous[n] returning the final list of distance return distance[], previous[] < pre> <p> <strong>Explanation:</strong> </p> <p>In the above pseudocode, we have defined a function that accepts multiple parameters - the Graph consisting of the nodes and the source node. Inside this function, we have iterated through each node in the Graph, set their initial distance to <strong>INFINITY</strong> , and set the previous node value to <strong>NULL</strong> . We have also checked whether any selected node is not a source node and added the same into the Priority Queue. Moreover, we have set the distance of the source node to <strong>0</strong> . We then iterated through the nodes in the priority queue, selected the node with the least distance, and marked it as visited. We then iterated through the unvisited neighboring nodes of the selected node and performed relaxation accordingly. At last, we have compared both the distances (original and temporary distance) between the source node and the destination node, updated the resultant distance with the minimum value and previous node information, and returned the final list of distances with their previous node information.</p> <h2>Implementation of Dijkstra&apos;s Algorithm in Different Programming Languages</h2> <p>Now that we have successfully understood the pseudocode of Dijkstra&apos;s Algorithm, it is time to see its implementation in different programming languages like C, C++, Java, and Python.</p> <h3>Code for Dijkstra&apos;s Algorithm in C</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the C Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.c</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in C // importing the standard I/O header file #include // defining some constants #define INF 9999 #define MAX 10 // prototyping of the function void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start); // defining the function for Dijkstra&apos;s Algorithm void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start) { int cost[MAX][MAX], distance[MAX], previous[MAX]; int visited_nodes[MAX], counter, minimum_distance, next_node, i, j; // creating cost matrix for (i = 0; i <size; i++) for (j="0;" j < size; j++) if (graph[i][j]="=" 0) cost[i][j]="INF;" else (i="0;" i { distance[i]="cost[start][i];" previous[i]="start;" visited_nodes[i]="0;" } distance[start]="0;" visited_nodes[start]="1;" counter="1;" while (counter size - 1) minimum_distance="INF;" (distance[i] && !visited_nodes[i]) next_node="i;" visited_nodes[next_node]="1;" (!visited_nodes[i]) (minimum_distance + cost[next_node][i] distance[i]) cost[next_node][i]; counter++; printing the distance !="start)" printf('
distance from source node to %d: %d', i, distance[i]); main function int main() defining variables graph[max][max], j, size, source; declaring of matrix nodes graph graph[0][0]="0;" graph[0][1]="4;" graph[0][2]="0;" graph[0][3]="0;" graph[0][4]="0;" graph[0][5]="8;" graph[0][6]="0;" graph[1][0]="4;" graph[1][1]="0;" graph[1][2]="8;" graph[1][3]="0;" graph[1][4]="0;" graph[1][5]="11;" graph[1][6]="0;" graph[2][0]="0;" graph[2][1]="8;" graph[2][2]="0;" graph[2][3]="7;" graph[2][4]="0;" graph[2][5]="4;" graph[2][6]="0;" graph[3][0]="0;" graph[3][1]="0;" graph[3][2]="7;" graph[3][3]="0;" graph[3][4]="9;" graph[3][5]="14;" graph[3][6]="0;" graph[4][0]="0;" graph[4][1]="0;" graph[4][2]="0;" graph[4][3]="9;" graph[4][4]="0;" graph[4][5]="10;" graph[4][6]="2;" graph[5][0]="0;" graph[5][1]="0;" graph[5][2]="4;" graph[5][3]="14;" graph[5][4]="10;" graph[5][5]="0;" graph[5][6]="2;" graph[6][0]="0;" graph[6][1]="0;" graph[6][2]="0;" graph[6][3]="0;" graph[6][4]="2;" graph[6][5]="0;" graph[6][6]="1;" calling dijkstraalgorithm() by passing graph, number and dijkstraalgorithm(graph, source); return 0; pre> <p> <strong>Output</strong> </p> <pre> Distance from the Source Node to 1: 4 Distance from the Source Node to 2: 12 Distance from the Source Node to 3: 19 Distance from the Source Node to 4: 12 Distance from the Source Node to 5: 8 Distance from the Source Node to 6: 10 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have included the <strong>stdio.h</strong> header file defined two constant values: <strong>INF = 9999</strong> and <strong>MAX = 10</strong> . We have declared the prototyping of the function and then defined the function for Dijkstra&apos;s Algorithm as <strong>DijkstraAlgorithm</strong> that accepts three arguments - the Graph consisting of the nodes, the number of nodes in the Graph, and the source node. Inside this function, we have defined some data structures such as a 2D matrix that will work as the Priority Queue for the algorithm, an array to main the distance between the nodes, an array to maintain the record of previous nodes, an array to store the visited nodes information, and some integer variables to store minimum distance value, counter, next node value and more. We then used a <strong>nested for-loop</strong> to iterate through the nodes of the Graph and add them to the priority queue accordingly. We have again used the <strong>for-loop</strong> to iterate through the elements in the priority queue starting from the source node and update their distances. Outside the loop, we have set the distance of the source node as <strong>0</strong> and marked it as visited in the <strong>visited_nodes[]</strong> array. We then set the counter value as one and used the <strong>while</strong> loop iterating through the number of nodes. Inside this loop, we have set the value of <strong>minimum_distance</strong> as <strong>INF</strong> and used the <strong>for-loop</strong> to update the value of the <strong>minimum_distance</strong> variable with the minimum value from a <strong>distance[]</strong> array. We then iterated through the unvisited neighboring nodes of the selected node using the <strong>for-loop</strong> and performed relaxation. We then printed the resulting data of the distances calculated using Dijkstra&apos;s Algorithm.</p> <p>In the <strong>main</strong> function, we have defined and declared the variables representing the Graph, the number of nodes, and the source node. At last, we have called the <strong>DijkstraAlgorithm()</strong> function by passing the required parameters.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in C++</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the C++ Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.cpp</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in C++ // importing the required header files #include #include // defining constant #define MAX_INT 10000000 // using the standard namespace using namespace std; // prototyping of the DijkstraAlgorithm() function void DijkstraAlgorithm(); // main function int main() { DijkstraAlgorithm(); return 0; } // declaring the classes class Vertex; class Edge; // prototyping the functions void Dijkstra(); vector* Adjacent_Remaining_Nodes(Vertex* vertex); Vertex* Extract_Smallest(vector&amp; vertices); int Distance(Vertex* vertexOne, Vertex* vertexTwo); bool Contains(vector&amp; vertices, Vertex* vertex); void Print_Shortest_Route_To(Vertex* des); // instantiating the classes vector vertices; vector edges; // defining the class for the vertices of the graph class Vertex { public: Vertex(char id) : id(id), prev(NULL), distance_from_start(MAX_INT) { vertices.push_back(this); } public: char id; Vertex* prev; int distance_from_start; }; // defining the class for the edges of the graph class Edge { public: Edge(Vertex* vertexOne, Vertex* vertexTwo, int distance) : vertexOne(vertexOne), vertexTwo(vertexTwo), distance(distance) { edges.push_back(this); } bool Connects(Vertex* vertexOne, Vertex* vertexTwo) public: Vertex* vertexOne; Vertex* vertexTwo; int distance; }; // defining the function to collect the details of the graph void DijkstraAlgorithm() { // declaring some vertices Vertex* vertex_a = new Vertex(&apos;A&apos;); Vertex* vertex_b = new Vertex(&apos;B&apos;); Vertex* vertex_c = new Vertex(&apos;C&apos;); Vertex* vertex_d = new Vertex(&apos;D&apos;); Vertex* vertex_e = new Vertex(&apos;E&apos;); Vertex* vertex_f = new Vertex(&apos;F&apos;); Vertex* vertex_g = new Vertex(&apos;G&apos;); // declaring some edges Edge* edge_1 = new Edge(vertex_a, vertex_c, 1); Edge* edge_2 = new Edge(vertex_a, vertex_d, 2); Edge* edge_3 = new Edge(vertex_b, vertex_c, 2); Edge* edge_4 = new Edge(vertex_c, vertex_d, 1); Edge* edge_5 = new Edge(vertex_b, vertex_f, 3); Edge* edge_6 = new Edge(vertex_c, vertex_e, 3); Edge* edge_7 = new Edge(vertex_e, vertex_f, 2); Edge* edge_8 = new Edge(vertex_d, vertex_g, 1); Edge* edge_9 = new Edge(vertex_g, vertex_f, 1); vertex_a -&gt; distance_from_start = 0; // setting a start vertex // calling the Dijkstra() function to find the shortest route possible Dijkstra(); // calling the Print_Shortest_Route_To() function to print the shortest route from the source vertex to the destination vertex Print_Shortest_Route_To(vertex_f); } // defining the function for Dijkstra&apos;s Algorithm void Dijkstra() { while (vertices.size() &gt; 0) { Vertex* smallest = Extract_Smallest(vertices); vector* adjacent_nodes = Adjacent_Remaining_Nodes(smallest); const int size = adjacent_nodes -&gt; size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest -&gt; distance_from_start; if (distance distance_from_start) { adjacent -&gt; distance_from_start = distance; adjacent -&gt; prev = smallest; } } delete adjacent_nodes; } } // defining the function to find the vertex with the shortest distance, removing it, and returning it Vertex* Extract_Smallest(vector&amp; vertices) { int size = vertices.size(); if (size == 0) return NULL; int smallest_position = 0; Vertex* smallest = vertices.at(0); for (int i = 1; i distance_from_start distance_from_start) { smallest = current; smallest_position = i; } } vertices.erase(vertices.begin() + smallest_position); return smallest; } // defining the function to return all vertices adjacent to &apos;vertex&apos; which are still in the &apos;vertices&apos; collection. vector* Adjacent_Remaining_Nodes(Vertex* vertex) { vector* adjacent_nodes = new vector(); const int size = edges.size(); for (int i = 0; i vertexOne == vertex) { adjacent = edge -&gt; vertexTwo; } else if (edge -&gt; vertexTwo == vertex) { adjacent = edge -&gt; vertexOne; } if (adjacent &amp;&amp; Contains(vertices, adjacent)) { adjacent_nodes -&gt; push_back(adjacent); } } return adjacent_nodes; } // defining the function to return distance between two connected vertices int Distance(Vertex* vertexOne, Vertex* vertexTwo) { const int size = edges.size(); for (int i = 0; i Connects(vertexOne, vertexTwo)) { return edge -&gt; distance; } } return -1; // should never happen } // defining the function to check if the &apos;vertices&apos; vector contains &apos;vertex&apos; bool Contains(vector&amp; vertices, Vertex* vertex) { const int size = vertices.size(); for (int i = 0; i <size; ++i) { if (vertex="=" vertices.at(i)) return true; } false; defining the function to print shortest route destination void print_shortest_route_to(vertex* des) vertex* prev="des;" cout << 'distance from start: ' < distance_from_start endl; while (prev) id prev; pre> <p> <strong>Output</strong> </p> <pre> Distance from start: 4 F G D A </pre> <p> <strong>Explanation:</strong> </p> <p>In the above code snippet, we included the <strong>&apos;iostream&apos;</strong> and <strong>&apos;vector&apos;</strong> header files and defined a constant value as <strong>MAX_INT = 10000000</strong> . We then used the standard namespace and prototyped the <strong>DijkstraAlgorithm()</strong> function. We then defined the main function of the program within, which we have called the <strong>DijkstraAlgorithm()</strong> function. After that, we declared some classes to create vertices and edges. We have also prototyped more functions to find the shortest possible path from the source vertex to the destination vertex and instantiated the Vertex and Edge classes. We then defined both classes to create the vertices and edges of the graph. We have then defined the <strong>DijkstraAlgorithm()</strong> function to create a graph and perform different operations. Inside this function, we have declared some vertices and edges. We then set the source vertex of the graph and called the <strong>Dijkstra()</strong> function to find the shortest possible distance and <strong>Print_Shortest_Route_To()</strong> function to print the shortest distance from the source vertex to vertex <strong>&apos;F&apos;</strong> . We have then defined the <strong>Dijkstra()</strong> function to calculate the shortest possible distances of the all the vertices from the source vertex. We have also defined some more functions to find the vertex with the shortest distance to return all the vertices adjacent to the remaining vertex, to return the distance between two connected vertices, to check if the selected vertex exists in the graph, and to print the shortest possible path from the source vertex to the destination vertex.</p> <p>As a result, the required shortest path for the vertex <strong>&apos;F&apos;</strong> from the source node is printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Java</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Java Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.java</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format('distance from %s to %s', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;></pre></size;></pre></size;></pre></distance[n]>

Explication:

Dans l'extrait de code ci-dessus, nous avons inclus le stdio.h Le fichier d'en-tête définit deux valeurs constantes : INF = 9999 et MAXIMUM = 10 . Nous avons déclaré le prototypage de la fonction, puis défini la fonction pour l'algorithme de Dijkstra comme Algorithme de Dijkstra qui accepte trois arguments : le graphique composé des nœuds, le nombre de nœuds dans le graphique et le nœud source. Dans cette fonction, nous avons défini certaines structures de données telles qu'une matrice 2D qui fonctionnera comme file d'attente prioritaire pour l'algorithme, un tableau pour gérer la distance entre les nœuds, un tableau pour conserver l'enregistrement des nœuds précédents, un tableau pour stocker les informations sur les nœuds visités et certaines variables entières pour stocker la valeur de distance minimale, le compteur, la valeur du nœud suivant et plus encore. Nous avons ensuite utilisé un boucle for imbriquée pour parcourir les nœuds du graphique et les ajouter à la file d'attente prioritaire en conséquence. Nous avons encore utilisé le boucle for pour parcourir les éléments de la file d'attente prioritaire à partir du nœud source et mettre à jour leurs distances. En dehors de la boucle, nous avons défini la distance du nœud source comme 0 et l'a marqué comme visité dans le nœuds_visités[] tableau. Nous avons ensuite défini la valeur du compteur sur un et utilisé le alors que boucle itérant sur le nombre de nœuds. Dans cette boucle, nous avons défini la valeur de distance_minimale comme INF et utilisé le boucle for pour mettre à jour la valeur du distance_minimale variable avec la valeur minimale d'un distance[] tableau. Nous avons ensuite parcouru les nœuds voisins non visités du nœud sélectionné en utilisant le boucle for et effectué une relaxation. Nous avons ensuite imprimé les données résultantes des distances calculées à l'aide de l'algorithme de Dijkstra.

Dans le principal fonction, nous avons défini et déclaré les variables représentant le graphe, le nombre de nœuds et le nœud source. Enfin, nous avons appelé le DijkstraAlgorithme() fonction en passant les paramètres requis.

En conséquence, les chemins les plus courts possibles requis pour chaque nœud à partir du nœud source sont imprimés pour les utilisateurs.

Code pour l'algorithme de Dijkstra en C++

Voici l'implémentation de l'algorithme de Dijkstra dans le langage de programmation C++ :

Fichier : DijkstraAlgorithm.cpp

 // Implementation of Dijkstra&apos;s Algorithm in C++ // importing the required header files #include #include // defining constant #define MAX_INT 10000000 // using the standard namespace using namespace std; // prototyping of the DijkstraAlgorithm() function void DijkstraAlgorithm(); // main function int main() { DijkstraAlgorithm(); return 0; } // declaring the classes class Vertex; class Edge; // prototyping the functions void Dijkstra(); vector* Adjacent_Remaining_Nodes(Vertex* vertex); Vertex* Extract_Smallest(vector&amp; vertices); int Distance(Vertex* vertexOne, Vertex* vertexTwo); bool Contains(vector&amp; vertices, Vertex* vertex); void Print_Shortest_Route_To(Vertex* des); // instantiating the classes vector vertices; vector edges; // defining the class for the vertices of the graph class Vertex { public: Vertex(char id) : id(id), prev(NULL), distance_from_start(MAX_INT) { vertices.push_back(this); } public: char id; Vertex* prev; int distance_from_start; }; // defining the class for the edges of the graph class Edge { public: Edge(Vertex* vertexOne, Vertex* vertexTwo, int distance) : vertexOne(vertexOne), vertexTwo(vertexTwo), distance(distance) { edges.push_back(this); } bool Connects(Vertex* vertexOne, Vertex* vertexTwo) public: Vertex* vertexOne; Vertex* vertexTwo; int distance; }; // defining the function to collect the details of the graph void DijkstraAlgorithm() { // declaring some vertices Vertex* vertex_a = new Vertex(&apos;A&apos;); Vertex* vertex_b = new Vertex(&apos;B&apos;); Vertex* vertex_c = new Vertex(&apos;C&apos;); Vertex* vertex_d = new Vertex(&apos;D&apos;); Vertex* vertex_e = new Vertex(&apos;E&apos;); Vertex* vertex_f = new Vertex(&apos;F&apos;); Vertex* vertex_g = new Vertex(&apos;G&apos;); // declaring some edges Edge* edge_1 = new Edge(vertex_a, vertex_c, 1); Edge* edge_2 = new Edge(vertex_a, vertex_d, 2); Edge* edge_3 = new Edge(vertex_b, vertex_c, 2); Edge* edge_4 = new Edge(vertex_c, vertex_d, 1); Edge* edge_5 = new Edge(vertex_b, vertex_f, 3); Edge* edge_6 = new Edge(vertex_c, vertex_e, 3); Edge* edge_7 = new Edge(vertex_e, vertex_f, 2); Edge* edge_8 = new Edge(vertex_d, vertex_g, 1); Edge* edge_9 = new Edge(vertex_g, vertex_f, 1); vertex_a -&gt; distance_from_start = 0; // setting a start vertex // calling the Dijkstra() function to find the shortest route possible Dijkstra(); // calling the Print_Shortest_Route_To() function to print the shortest route from the source vertex to the destination vertex Print_Shortest_Route_To(vertex_f); } // defining the function for Dijkstra&apos;s Algorithm void Dijkstra() { while (vertices.size() &gt; 0) { Vertex* smallest = Extract_Smallest(vertices); vector* adjacent_nodes = Adjacent_Remaining_Nodes(smallest); const int size = adjacent_nodes -&gt; size(); for (int i = 0; i at(i); int distance = Distance(smallest, adjacent) + smallest -&gt; distance_from_start; if (distance distance_from_start) { adjacent -&gt; distance_from_start = distance; adjacent -&gt; prev = smallest; } } delete adjacent_nodes; } } // defining the function to find the vertex with the shortest distance, removing it, and returning it Vertex* Extract_Smallest(vector&amp; vertices) { int size = vertices.size(); if (size == 0) return NULL; int smallest_position = 0; Vertex* smallest = vertices.at(0); for (int i = 1; i distance_from_start distance_from_start) { smallest = current; smallest_position = i; } } vertices.erase(vertices.begin() + smallest_position); return smallest; } // defining the function to return all vertices adjacent to &apos;vertex&apos; which are still in the &apos;vertices&apos; collection. vector* Adjacent_Remaining_Nodes(Vertex* vertex) { vector* adjacent_nodes = new vector(); const int size = edges.size(); for (int i = 0; i vertexOne == vertex) { adjacent = edge -&gt; vertexTwo; } else if (edge -&gt; vertexTwo == vertex) { adjacent = edge -&gt; vertexOne; } if (adjacent &amp;&amp; Contains(vertices, adjacent)) { adjacent_nodes -&gt; push_back(adjacent); } } return adjacent_nodes; } // defining the function to return distance between two connected vertices int Distance(Vertex* vertexOne, Vertex* vertexTwo) { const int size = edges.size(); for (int i = 0; i Connects(vertexOne, vertexTwo)) { return edge -&gt; distance; } } return -1; // should never happen } // defining the function to check if the &apos;vertices&apos; vector contains &apos;vertex&apos; bool Contains(vector&amp; vertices, Vertex* vertex) { const int size = vertices.size(); for (int i = 0; i <size; ++i) { if (vertex="=" vertices.at(i)) return true; } false; defining the function to print shortest route destination void print_shortest_route_to(vertex* des) vertex* prev="des;" cout << \'distance from start: \' < distance_from_start endl; while (prev) id prev; pre> <p> <strong>Output</strong> </p> <pre> Distance from start: 4 F G D A </pre> <p> <strong>Explanation:</strong> </p> <p>In the above code snippet, we included the <strong>&apos;iostream&apos;</strong> and <strong>&apos;vector&apos;</strong> header files and defined a constant value as <strong>MAX_INT = 10000000</strong> . We then used the standard namespace and prototyped the <strong>DijkstraAlgorithm()</strong> function. We then defined the main function of the program within, which we have called the <strong>DijkstraAlgorithm()</strong> function. After that, we declared some classes to create vertices and edges. We have also prototyped more functions to find the shortest possible path from the source vertex to the destination vertex and instantiated the Vertex and Edge classes. We then defined both classes to create the vertices and edges of the graph. We have then defined the <strong>DijkstraAlgorithm()</strong> function to create a graph and perform different operations. Inside this function, we have declared some vertices and edges. We then set the source vertex of the graph and called the <strong>Dijkstra()</strong> function to find the shortest possible distance and <strong>Print_Shortest_Route_To()</strong> function to print the shortest distance from the source vertex to vertex <strong>&apos;F&apos;</strong> . We have then defined the <strong>Dijkstra()</strong> function to calculate the shortest possible distances of the all the vertices from the source vertex. We have also defined some more functions to find the vertex with the shortest distance to return all the vertices adjacent to the remaining vertex, to return the distance between two connected vertices, to check if the selected vertex exists in the graph, and to print the shortest possible path from the source vertex to the destination vertex.</p> <p>As a result, the required shortest path for the vertex <strong>&apos;F&apos;</strong> from the source node is printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Java</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Java Programming Language:</p> <p> <strong>File: DijkstraAlgorithm.java</strong> </p> <pre> // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format(\'distance from %s to %s\', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;></pre></size;>

Explication:

Dans l'extrait de code ci-dessus, nous avons inclus le 'iostream' et 'vecteur' fichiers d'en-tête et défini une valeur constante comme MAX_INT = 1 0000000 . Nous avons ensuite utilisé l'espace de noms standard et prototypé le DijkstraAlgorithme() fonction. Nous avons ensuite défini la fonction principale du programme, que nous avons appelé le DijkstraAlgorithme() fonction. Après cela, nous avons déclaré certaines classes pour créer des sommets et des arêtes. Nous avons également prototypé davantage de fonctions pour trouver le chemin le plus court possible entre le sommet source et le sommet de destination et instancié les classes Vertex et Edge. Nous avons ensuite défini les deux classes pour créer les sommets et les arêtes du graphe. Nous avons ensuite défini le DijkstraAlgorithme() fonction pour créer un graphique et effectuer différentes opérations. Dans cette fonction, nous avons déclaré certains sommets et arêtes. Nous définissons ensuite le sommet source du graphe et appelons le Dijkstra() fonction pour trouver la distance la plus courte possible et Print_Shortest_Route_To() fonction pour imprimer la distance la plus courte du sommet source au sommet 'F' . Nous avons ensuite défini le Dijkstra() fonction pour calculer les distances les plus courtes possibles de tous les sommets à partir du sommet source. Nous avons également défini quelques fonctions supplémentaires pour trouver le sommet avec la distance la plus courte pour renvoyer tous les sommets adjacents au sommet restant, pour renvoyer la distance entre deux sommets connectés, pour vérifier si le sommet sélectionné existe dans le graphique et pour imprimer le chemin le plus court possible du sommet source au sommet de destination.

En conséquence, le chemin le plus court requis pour le sommet 'F' du nœud source est imprimé pour les utilisateurs.

Code pour l'algorithme de Dijkstra en Java

Voici l'implémentation de l'algorithme de Dijkstra dans le langage de programmation Java :

Fichier : DijkstraAlgorithm.java

 // Implementation of Dijkstra&apos;s Algorithm in Java // defining the public class for Dijkstra&apos;s Algorithm public class DijkstraAlgorithm { // defining the method to implement Dijkstra&apos;s Algorithm public void dijkstraAlgorithm(int[][] graph, int source) { // number of nodes int nodes = graph.length; boolean[] visited_vertex = new boolean[nodes]; int[] dist = new int[nodes]; for (int i = 0; i <nodes; 0 1 i++) { visited_vertex[i]="false;" dist[i]="Integer.MAX_VALUE;" } distance of self loop is zero dist[source]="0;" for (int i="0;" < nodes; updating the between neighboring vertex and source int u="find_min_distance(dist," visited_vertex); visited_vertex[u]="true;" distances all vertices v="0;" v++) if (!visited_vertex[v] && graph[u][v] !="0" (dist[u] + dist[v])) dist[v]="dist[u]" graph[u][v]; dist.length; system.out.println(string.format(\'distance from %s to %s\', source, i, dist[i])); defining method find minimum private static find_min_distance(int[] dist, boolean[] visited_vertex) minimum_distance="Integer.MAX_VALUE;" minimum_distance_vertex="-1;" (!visited_vertex[i] minimum_distance) return minimum_distance_vertex; main function public void main(string[] args) declaring nodes graphs graph[][]="new" int[][] 0, 1, 2, }, 3, }; instantiating dijkstraalgorithm() class dijkstraalgorithm test="new" dijkstraalgorithm(); calling shortest node destination test.dijkstraalgorithm(graph, 0); pre> <p> <strong>Output</strong> </p> <pre> Distance from Vertex 0 to Vertex 0 is 0 Distance from Vertex 0 to Vertex 1 is 1 Distance from Vertex 0 to Vertex 2 is 1 Distance from Vertex 0 to Vertex 3 is 2 Distance from Vertex 0 to Vertex 4 is 4 Distance from Vertex 0 to Vertex 5 is 4 Distance from Vertex 0 to Vertex 6 is 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have defined a public class as <strong>DijkstraAlgorithm()</strong> . Inside this class, we have defined a public method as <strong>dijkstraAlgorithm()</strong> to find the shortest distance from the source vertex to the destination vertex. Inside this method, we have defined a variable to store the number of nodes. We have then defined a Boolean array to store the information regarding the visited vertices and an integer array to store their respective distances. Initially, we declared the values in both the arrays as <strong>False</strong> and <strong>MAX_VALUE</strong> , respectively. We have also set the distance of the source vertex as zero and used the <strong>for-loop</strong> to update the distance between the source vertex and destination vertices with the minimum distance. We have then updated the distances of the neighboring vertices of the selected vertex by performing relaxation and printed the shortest distances for every vertex. We have then defined a method to find the minimum distance from the source vertex to the destination vertex. We then defined the main function where we declared the vertices of the graph and instantiated the <strong>DijkstraAlgorithm()</strong> class. Finally, we have called the <strong>dijkstraAlgorithm()</strong> method to find the shortest distance between the source vertex and the destination vertices.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h3>Code for Dijkstra&apos;s Algorithm in Python</h3> <p>The following is the implementation of Dijkstra&apos;s Algorithm in the Python Programming Language:</p> <p> <strong>File: DikstraAlgorithm.py</strong> </p> <pre> # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0></pre> <p> <strong>Output</strong> </p> <pre> Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above snippet of code, we have imported the <strong>sys</strong> module and declared the lists consisting of the values for the nodes and edges. We have then defined a function as <strong>toBeVisited()</strong> to find which node will be visited next. We then found the total number of nodes in the graph and set the initial distances for every node. We have then calculated the minimum distance from the source node to the destination node, performed relaxation on neighboring nodes, and updated the distances in the list. We then printed those distances from the list for the users.</p> <p>As a result, the required shortest possible paths for every node from the source node are printed for the users.</p> <h2>Time and Space Complexity of Dijkstra&apos;s Algorithm</h2> <ul> <li>The Time Complexity of Dijkstra&apos;s Algorithm is <strong>O(E log V)</strong> , where E is the number of edges and V is the number of vertices.</li> <li>The Space Complexity of Dijkstra&apos;s Algorithm is O(V), where V is the number of vertices.</li> </ul> <h2>Advantages and Disadvantages of Dijkstra&apos;s Algorithm</h2> <p> <strong>Let us discuss some advantages of Dijkstra&apos;s Algorithm:</strong> </p> <ol class="points"> <li>One primary advantage of using Dijkstra&apos;s Algorithm is that it has an almost linear time and space complexity.</li> <li>We can use this algorithm to calculate the shortest path from a single vertex to all other vertices and a single source vertex to a single destination vertex by stopping the algorithm once we get the shortest distance for the destination vertex.</li> <li>This algorithm only works for directed weighted graphs, and all the edges of this graph should be non-negative.</li> </ol> <p> <strong>Despite having multiple advantages, Dijkstra&apos;s algorithm has some disadvantages also, such as:</strong> </p> <ol class="points"> <li>Dijkstra&apos;s Algorithm performs a concealed exploration that utilizes a lot of time during the process.</li> <li>This algorithm is impotent to handle negative edges.</li> <li>Since this algorithm heads to the acyclic graph, it cannot calculate the exact shortest path.</li> <li>It also requires maintenance to keep a record of vertices that have been visited.</li> </ol> <h2>Some Applications of Dijkstra&apos;s Algorithm</h2> <p> <strong>Dijkstra&apos;s Algorithm has various real-world applications, some of which are stated below:</strong> </p> <ol class="points"> <tr><td>Digital Mapping Services in Google Maps:</td> There are various times when we have tried to find the distance in Google Maps either from our location to the nearest preferred location or from one city to another, which comprises multiple routes/paths connecting them; however, the application must display the minimum distance. This is only possible because Dijkstra&apos;s algorithm helps the application find the shortest between two given locations along the path. Let us consider the USA as a graph wherein the cities/places are represented as vertices, and the routes between two cities/places are represented as edges. Then with the help of Dijkstra&apos;s Algorithm, we can calculate the shortest routes between any two cities/places. </tr><tr><td>Social Networking Applications:</td> In many applications like Facebook, Twitter, Instagram, and more, many of us might have observed that these apps suggest the list of friends that a specific user may know. How do many social media companies implement this type of feature in an efficient and effective way, specifically when the system has over a billion users? The answer to this question is Dijkstra&apos;s Algorithm. The standard Dijkstra&apos;s Algorithm is generally used to estimate the shortest distance between the users measured through the connections or mutuality among them. When social networking is very small, it uses the standard Dijkstra&apos;s Algorithm in addition to some other features in order to determine the shortest paths. However, when the graph is much bigger, the standard algorithm takes several seconds to count, and thus, some advanced algorithms are used as the alternative. </tr><tr><td>Telephone Network:</td> As some of us might know, in a telephone network, each transmission line has a bandwidth, &apos;b&apos;. The bandwidth is the highest frequency that the transmission line can support. In general, if the frequency of the signal is higher in a specific line, the signal is reduced by that line. Bandwidth represents the amount of information that can be transmitted by the line. Let us consider a city a graph wherein the switching stations are represented using the vertices, the transmission lines are represented as the edges, and the bandwidth, &apos;b&apos;, is represented using the weight of the edges. Thus, as we can observe, the telephone network can also fall into the category of the shortest distance problem and can be solved using Dijkstra&apos;s Algorithm. </tr><tr><td>Flight Program:</td> Suppose that a person requires software to prepare an agenda of flights for customers. The agent has access to a database with all flights and airports. In addition to the flight number, origin airport, and destination, the flights also have departure and arrival times. So, in order to determine the earliest arrival time for the selected destination from the original airport and given start time, the agents make use of Dijkstra&apos;s Algorithm. </tr><tr><td>IP routing to find Open Shortest Path First:</td> Open Shortest Path First (abbreviated as OSPF) is a link-state routing protocol used to find the best path between the source and destination router with the help of its own Shortest Path First. Dijkstra&apos;s Algorithm is extensively utilized in the routing protocols required by the routers in order to update their forwarding table. The algorithm gives the shortest cost path from the source router to the other routers present in the network. </tr><tr><td>Robotic Path:</td> These days, drones and robots have come into existence, some operated manually and some automatically. The drones and robots which are operated automatically and used to deliver the packages to a given location or used for any certain task are configured with Dijkstra&apos;s Algorithm module so that whenever the source and destination are known, the drone and robot will move in the ordered direction by following the shortest path keeping the time taken to a minimum in order to deliver the packages. </tr><tr><td>Designate the File Server:</td> Dijkstra&apos;s Algorithm is also used to designate a file server in a Local Area Network (LAN). Suppose that an infinite period of time is needed for the transmission of the files from one computer to another. So, to minimize the number of &apos;hops&apos; from the file server to every other computer on the network, we will use Dijkstra&apos;s Algorithm. This algorithm will return the shortest path between the networks resulting in the minimum number of hops. </tr></ol> <h2>The Conclusion</h2> <ul> <li>In the above tutorial, firstly, we have understood the basic concepts of Graph along with its types and applications.</li> <li>We then learned about Dijkstra&apos;s Algorithm and its history.</li> <li>We have also understood the fundamental working of Dijkstra&apos;s Algorithm with the help of an example.</li> <li>After that, we studied how to write code for Dijkstra&apos;s Algorithm with the help of Pseudocode.</li> <li>We observed its implementation in programming languages like C, C++, Java, and Python with proper outputs and explanations.</li> <li>We have also understood the Time and Space Complexity of Dijkstra&apos;s Algorithm.</li> <li>Finally, we have discussed the advantages and disadvantages of Dijkstra&apos;s algorithm and some of its real-life applications.</li> </ul> <hr></nodes;>

Explication:

Dans l'extrait de code ci-dessus, nous avons défini une classe publique comme DijkstraAlgorithme() . Dans cette classe, nous avons défini une méthode publique comme dijkstraAlgorithme() pour trouver la distance la plus courte entre le sommet source et le sommet de destination. Dans cette méthode, nous avons défini une variable pour stocker le nombre de nœuds. Nous avons ensuite défini un tableau booléen pour stocker les informations concernant les sommets visités et un tableau d'entiers pour stocker leurs distances respectives. Initialement, nous avons déclaré les valeurs des deux tableaux comme FAUX et VALEUR MAX , respectivement. Nous avons également fixé la distance du sommet source à zéro et utilisé la boucle for pour mettre à jour la distance entre le sommet source et les sommets de destination avec la distance minimale. Nous avons ensuite mis à jour les distances des sommets voisins du sommet sélectionné en effectuant une relaxation et imprimé les distances les plus courtes pour chaque sommet. Nous avons ensuite défini une méthode pour trouver la distance minimale du sommet source au sommet de destination. Nous avons ensuite défini la fonction principale où nous avons déclaré les sommets du graphe et instancié le DijkstraAlgorithme() classe. Enfin, nous avons appelé le dijkstraAlgorithme() méthode pour trouver la distance la plus courte entre le sommet source et les sommets de destination.

En conséquence, les chemins les plus courts possibles requis pour chaque nœud à partir du nœud source sont imprimés pour les utilisateurs.

Code pour l'algorithme de Dijkstra en Python

Voici l'implémentation de l'algorithme de Dijkstra dans le langage de programmation Python :

Fichier : DikstraAlgorithm.py

 # Implementation of Dijkstra&apos;s Algorithm in Python # importing the sys module import sys # declaring the list of nodes for the graph nodes = [ [0, 0, 1, 0, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # declaring the list of edges for the graph edges = [ [0, 0, 1, 0, 2, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0] ] # defining the function to find which node is to be visited next def toBeVisited(): global visitedAndDistance v = -10 for index in range(numberOfNodes): if visitedAndDistance[index][0] == 0 and (v <0 1 or visitedanddistance[index][1] <="visitedAndDistance[v][1]):" v="index" return # finding the number of nodes in graph numberofnodes="len(nodes[0])" visitedanddistance="[[0," 0]] for i range(numberofnodes - 1): visitedanddistance.append([0, sys.maxsize]) node range(numberofnodes): next to be visited tovisit="toBeVisited()" neighborindex updating new distances if nodes[tovisit][neighborindex]="=" and visitedanddistance[neighborindex][0]="=" 0: newdistance="visitedAndDistance[toVisit][1]" + edges[tovisit][neighborindex] visitedanddistance[neighborindex][1]> newDistance: visitedAndDistance[neighborIndex][1] = newDistance visitedAndDistance[toVisit][0] = 1 i = 0 # printing the distance for distance in visitedAndDistance: print(&apos;Distance of&apos;, chr(ord(&apos;A&apos;) + i), &apos;from source node:&apos;, distance[1]) i = i + 1 </0>

Sortir

 Distance of A from source node: 0 Distance of B from source node: 3 Distance of C from source node: 1 Distance of D from source node: 2 Distance of E from source node: 2 Distance of F from source node: 4 Distance of G from source node: 3

Explication:

Dans l'extrait de code ci-dessus, nous avons importé le système module et a déclaré les listes constituées des valeurs des nœuds et des arêtes. Nous avons alors défini une fonction comme à visiter() pour trouver quel nœud sera visité ensuite. Nous avons ensuite trouvé le nombre total de nœuds dans le graphique et défini les distances initiales pour chaque nœud. Nous avons ensuite calculé la distance minimale du nœud source au nœud destination, effectué une relaxation sur les nœuds voisins et mis à jour les distances dans la liste. Nous avons ensuite imprimé ces distances à partir de la liste pour les utilisateurs.

En conséquence, les chemins les plus courts possibles requis pour chaque nœud à partir du nœud source sont imprimés pour les utilisateurs.

Complexité temporelle et spatiale de l'algorithme de Dijkstra

La complexité temporelle de l'algorithme de Dijkstra est O (E log V) , où E est le nombre d'arêtes et V est le nombre de sommets.
La complexité spatiale de l'algorithme de Dijkstra est O(V), où V est le nombre de sommets.

Avantages et inconvénients de l'algorithme de Dijkstra

Discutons de quelques avantages de l'algorithme de Dijkstra :

L’un des principaux avantages de l’utilisation de l’algorithme de Dijkstra est qu’il présente une complexité temporelle et spatiale presque linéaire.
Nous pouvons utiliser cet algorithme pour calculer le chemin le plus court d'un seul sommet à tous les autres sommets et d'un seul sommet source à un seul sommet de destination en arrêtant l'algorithme une fois que nous obtenons la distance la plus courte pour le sommet de destination.
Cet algorithme ne fonctionne que pour les graphiques à pondération dirigée, et toutes les arêtes de ce graphique doivent être non négatives.

Malgré ses multiples avantages, l'algorithme de Dijkstra présente également certains inconvénients, tels que :

L'algorithme de Dijkstra effectue une exploration cachée qui prend beaucoup de temps pendant le processus.
Cet algorithme est impuissant à gérer les fronts négatifs.
Puisque cet algorithme se dirige vers le graphe acyclique, il ne peut pas calculer exactement le chemin le plus court.
Cela nécessite également une maintenance pour conserver un enregistrement des sommets visités.

Quelques applications de l'algorithme de Dijkstra

L'algorithme de Dijkstra a diverses applications dans le monde réel, dont certaines sont indiquées ci-dessous :

Services de cartographie numérique dans Google Maps :Il y a plusieurs fois où nous avons essayé de trouver la distance dans Google Maps soit de notre emplacement à l'emplacement préféré le plus proche, soit d'une ville à une autre, qui comprend plusieurs itinéraires/chemins les reliant ; cependant, l'application doit afficher la distance minimale. Cela n'est possible que parce que l'algorithme de Dijkstra aide l'application à trouver le plus court entre deux emplacements donnés le long du chemin. Considérons les États-Unis comme un graphique dans lequel les villes/lieux sont représentés par des sommets, et les routes entre deux villes/lieux sont représentées par des arêtes. Ensuite, avec l'aide de l'algorithme de Dijkstra, nous pouvons calculer les itinéraires les plus courts entre deux villes/lieux.Applications de réseaux sociaux :Dans de nombreuses applications comme Facebook, Twitter, Instagram et bien d’autres, beaucoup d’entre nous ont peut-être remarqué que ces applications suggèrent la liste d’amis qu’un utilisateur spécifique peut connaître. Comment de nombreuses entreprises de médias sociaux mettent-elles en œuvre ce type de fonctionnalité de manière efficace et efficiente, en particulier lorsque le système compte plus d'un milliard d'utilisateurs ? La réponse à cette question est l’algorithme de Dijkstra. L'algorithme standard de Dijkstra est généralement utilisé pour estimer la distance la plus courte entre les utilisateurs mesurée via les connexions ou la mutualité entre eux. Lorsque le réseau social est très petit, il utilise l'algorithme standard de Dijkstra en plus de quelques autres fonctionnalités afin de déterminer les chemins les plus courts. Cependant, lorsque le graphique est beaucoup plus grand, l’algorithme standard met plusieurs secondes à compter et certains algorithmes avancés sont donc utilisés comme alternative.Réseau téléphonique:Comme certains d'entre nous le savent peut-être, dans un réseau téléphonique, chaque ligne de transmission possède une bande passante « b ». La bande passante est la fréquence la plus élevée que la ligne de transmission peut prendre en charge. En général, si la fréquence du signal est plus élevée dans une ligne spécifique, le signal est réduit de cette ligne. La bande passante représente la quantité d'informations pouvant être transmise par la ligne. Considérons une ville comme un graphique dans lequel les stations de commutation sont représentées à l'aide des sommets, les lignes de transmission sont représentées par les arêtes et la bande passante «b» est représentée à l'aide du poids des arêtes. Ainsi, comme nous pouvons le constater, le réseau téléphonique peut également entrer dans la catégorie du problème de distance la plus courte et peut être résolu à l'aide de l'algorithme de Dijkstra.Programme de vol :Supposons qu'une personne ait besoin d'un logiciel pour préparer un agenda de vols pour ses clients. L'agent a accès à une base de données avec tous les vols et aéroports. En plus du numéro de vol, de l'aéroport d'origine et de destination, les vols ont également des heures de départ et d'arrivée. Ainsi, afin de déterminer l'heure d'arrivée la plus précoce pour la destination sélectionnée depuis l'aéroport d'origine et l'heure de départ donnée, les agents utilisent l'algorithme de Dijkstra.Routage IP pour trouver le chemin le plus court ouvert en premier :Open Shortest Path First (en abrégé OSPF) est un protocole de routage à état de lien utilisé pour trouver le meilleur chemin entre le routeur source et le routeur de destination à l'aide de son propre Shortest Path First. L'algorithme de Dijkstra est largement utilisé dans les protocoles de routage requis par les routeurs afin de mettre à jour leur table de transfert. L'algorithme donne le chemin de coût le plus court depuis le routeur source vers les autres routeurs présents dans le réseau.Chemin robotique :De nos jours, des drones et des robots ont vu le jour, certains fonctionnant manuellement et d’autres automatiquement. Les drones et robots qui fonctionnent automatiquement et utilisés pour livrer les colis à un endroit donné ou utilisés pour une tâche spécifique sont configurés avec le module d'algorithme de Dijkstra de sorte que chaque fois que la source et la destination sont connues, le drone et le robot se déplacent dans la direction ordonnée. en suivant le chemin le plus court en gardant le temps nécessaire à la livraison des colis au minimum.Désignez le serveur de fichiers :L'algorithme de Dijkstra est également utilisé pour désigner un serveur de fichiers dans un réseau local (LAN). Supposons qu'une période de temps infinie soit nécessaire pour la transmission des fichiers d'un ordinateur à un autre. Ainsi, pour minimiser le nombre de « sauts » entre le serveur de fichiers et tous les autres ordinateurs du réseau, nous utiliserons l'algorithme de Dijkstra. Cet algorithme renverra le chemin le plus court entre les réseaux, ce qui entraînera le nombre minimum de sauts.

La conclusion

Dans le didacticiel ci-dessus, nous avons tout d’abord compris les concepts de base de Graph ainsi que ses types et applications.
Nous avons ensuite découvert l'algorithme de Dijkstra et son histoire.
Nous avons également compris le fonctionnement fondamental de l'algorithme de Dijkstra à l'aide d'un exemple.
Après cela, nous avons étudié comment écrire du code pour l'algorithme de Dijkstra à l'aide du pseudocode.
Nous avons observé son implémentation dans des langages de programmation comme C, C++, Java et Python avec des sorties et des explications appropriées.
Nous avons également compris la complexité temporelle et spatiale de l'algorithme de Dijkstra.
Enfin, nous avons discuté des avantages et des inconvénients de l'algorithme de Dijkstra et de certaines de ses applications réelles.