Complexité temporelle de l'algorithme de Dijkstra

«L'algorithme de Dijkstra recherche le chemin le plus court entre deux nœuds dans un graphique. Le nœud est également appelé sommet dans les œuvres graphiques. Une branche dans un graphique est également appelée bord. Pour plus de simplicité, le programme de cet article recherchera le chemin le plus court entre un sommet source et un sommet de destination."

Considérez les villes suivantes: A, B, C, D, E et F reliées par les routes:

Ces villes sont reliées par les routes (qui peuvent être supposées être droites). La longueur de la route de la ville A à la ville B est de 4 unités; il n'est pas tiré à l'échelle. La longueur de la route de la ville A à la ville C est de 5 unités; il n'est pas tiré à l'échelle. La longueur de la ville B à la ville E est de 11 unités, non attirée à l'échelle. Les routes entre les autres villes sont également indiquées.

Les villes: A, B, C, D, E et F sont les sommets d'un graphique. Les routes sont les bords du graphique. Cependant, ce graphique sera représenté dans une structure de données mathématique, différemment de sa disposition géographique.

L'algorithme de Dijkstra peut être utilisé pour trouver le chemin le plus court entre un sommet source (disons a) et tout autre sommet. Pour plus de simplicité, cet article visera à rechercher le chemin le plus court de A à E.

Il existe différents chemins de A à E, avec différentes longueurs, comme suit:

A-b-d-f: 4 + 9 + 2 = 15
A-b-e-f: 4 + 7 + 6 = 17
A-B-C-E-F: 4 + 11 + 3 + 6 = 24
A-b-c-e-d-f: 4 + 11 + 3 + 13 + 2 = 33
A-b-d-e-f: 4 + 9 + 13 + 6 = 32
A-b-e-d-f: 4 + 7 + 13 + 2 = 26
A-C-E-F: 5 + 3 + 6 = 14
A-c-b-d-f: 5 + 11 + 9 + 2 = 27
A-C-B-E-F: 5 + 11 + 7 + 6 = 29
A-C-B-E-F: 5 + 11 + 7 + 6 = 29
A-C-E-D-F: 5 + 3 + 13 + 2 = 14
A-C-B-E-D-F: 5 + 11 + 7 + 13 + 2 = 38

À partir de cette liste, le chemin le plus court est A-C-E-F, avec une longueur totale de 14 unités.

L'objectif principal de cet article est de trouver le temps d'exécution que l'algorithme de Dijkstra prend pour obtenir le chemin le plus court de A à E. Le temps ne sera pas donné en quelques secondes ou minutes. C'est le temps d'exécution total relatif, appelé complexité temporelle, qui sera donné. Le codage C ++ est également fourni.

Graphique à utiliser

La complexité temporelle (temps d'exécution relatif) dépend principalement du type de graphique mathématique utilisé pour représenter la disposition géographique. Cela dépend également de l'algorithme (un autre type d'algorithme) utilisé pour trier les sommets voisins de chaque sommet dans l'algorithme global (algorithme de Dijkstra). Le tri des sommets voisins n'est pas abordé dans cet article.

Le graphique mathématique choisi pour cet article est appelé matrice d'adjacence. C'est:

Les en-têtes de ligne sont les noms de la ville de A à F. Les en-têtes de colonne sont les mêmes noms de ville de A à F. Chaque entrée est la longueur d'une route d'une ville à l'autre. La longueur d'une route d'une ville à elle-même est zéro. La longueur d'une route d'une ville à une autre, après avoir sauté une ou plusieurs villes, est également nulle. Seules les routes directes sont considérées. Chaque entrée est située, d'abord par ligne puis par colonne. Encore une fois, chaque entrée est la longueur d'une route, sans sauter une ville, et non à la ville elle-même. Cette matrice est une représentation mathématique du réseau géographique donné ci-dessus.

Ainsi, la matrice se compose de bords, avec les en-têtes de ligne et de colonne des mêmes sommets. La matrice est la structure principale nécessaire dans le programme. Deux autres vecteurs (tableaux) sont utilisés dans ce programme de base.

Algorithme de Dijkstra

L'algorithme de Dijkstra recherche le chemin le plus court entre deux sommets dans un graphique (réseau). La matrice ci-dessus est le graphique, qui correspond au réseau géographique ci-dessus. Pour plus de simplicité, le programme de cet article recherchera le chemin le plus court entre un sommet source et un sommet de destination. Précisément, le programme recherchera le chemin le plus court du sommet source, A, au sommet de destination, f.

L'algorithme, tel qu'il est pertinent pour cette tâche, est le suivant:

- Tous les sommets sont marqués comme non visité. À ce stade, un ensemble de tous les sommets non visitées sont créés.

- Attribuez une valeur de longueur de chemin provisoire à tous les sommets: la longueur du chemin de la source à la source se voit attribuer une valeur de zéro; La longueur du chemin de la source à tout autre sommet se voit attribuer la seule valeur de l'infini, i.e., une valeur supérieure à la voie la plus élevée possible, dans le graphique. La valeur de chaque sommet serait modifiée au moins une fois, d'une valeur élevée à une valeur inférieure, car l'algorithme continue. Les sommets possibles pour le chemin le plus court complet seront axés sur, à partir du sommet source (a). Le sommet avec le foyer est appelé le sommet actuel. Le sommet actuel a des voisins, mieux visualisés à partir du réseau réel (disposition géographique) ci-dessus.

- Il y a le sommet actuel, et il y a le sommet visité. En fait, il y aurait plus d'un sommet visité dans une chaîne alors que l'algorithme continue. Tous les sommets précédents considérés comme visités sont sur le chemin le plus court qui est en cours de développement, à partir de la source. La longueur du chemin du dernier sommet visité est connue (doit être connue). Un sommet est déclaré visité lorsque sa longueur de chemin est confirmée. Le sommet visité donne le moins de longueur de chemin de la source jusqu'à présent, car l'algorithme est en cours. Les voisins non visités du sommet actuel, à l'exception de son prochain voisin immédiat visité, ont des valeurs provisoires (longueurs de chemin de la source), dont certaines peuvent encore être l'infini (valeur très élevée). Pour chaque voisin non visité et le sommet actuel, une nouvelle longueur de chemin provisoire est calculée comme suit: la longueur du chemin du sommet du sommet précédemment visité, plus la longueur du bord vers le sommet actuel, plus la longueur du bord du sommet actuel, vers la voisin non visité. Si ce résultat est inférieur à ce qui était là, car la longueur de chemin provisoire de la source au voisin non visité du sommet actuel, alors cette valeur calculée devient la nouvelle valeur provisoire pour le voisin du sommet actuel. C'est-à-dire que la nouvelle valeur de chemin provisoire pour un sommet non visité est calculée à travers le sommet actuel à partir du sommet précédemment visité.

- Il peut y avoir plus d'un sommet actuel. Lorsque tous les voisins de chaque sommet actuel ont été accessibles et que l'on considère de nouvelles longueurs de chemin provisoire appropriées, le sommet actuel avec la moindre longueur de chemin à partir de la source (moins de valeur) est considéré comme visité. Puisqu'il avait la moindre valeur, sa moindre valeur est confirmée comme la longueur de chemin de partie la plus courte jusqu'à présent. Le sommet précédemment visité est supprimé de l'ensemble de sommet non visité. Un sommet visité ne sera plus jamais vérifié. Toutes les visites après auraient une plus grande longueur de chemin.

- Les deux étapes précédentes sont répétées, dans l'ordre, pour tout sommet actuel qui devient un sommet visité. Cette répétition se poursuit jusqu'à ce que le sommet de destination soit atteint. Le sommet de destination peut être n'importe quel sommet après le sommet source. Cependant, pour simplicité, le dernier sommet, F du réseau ci-dessus, a été choisi comme sommet de destination pour cet article.

- Au fur et à mesure que l'algorithme progresse, chaque sommet parent (précédemment visité), et chaque sommet (suivi suivant) du chemin le plus court devrait être enregistré en cas de trajet le plus court, par sommet, ainsi que le chemin le plus court selon la longueur, est nécessaire (est nécessaire (est nécessaire (est nécessaire (est nécessaire (est nécessaire (est nécessaire (est nécessaire (est nécessaire (est nécessaire (est nécessaire ( demandé). Lorsque le sommet de destination est atteint et visité, le chemin le plus court complet peut être tracé vers l'arrière si le chemin par des sommets est nécessaire. Quant à la longueur du chemin, il a été calculé à mesure que l'algorithme progressait.

Illustration algorithme de Dijkstra

La route ci-dessus

Le réseau est utilisé pour illustrer l'algorithme de Dijkstra. Il est redéfini ci-dessous pour une référence facile.

Il commence à la source «A» avec une longueur de chemin de zéro. «A» est considéré comme visité et supprimé de la liste non visitée (SET). «A» est envoyé à une liste visitée au cas où le chemin par des sommets sera requis.

Les longueurs de chemin de A à B sont:

A-b = 4
A-c-b = 5 + 11 = 16

Entre 4, 16, et l'infini (c'était là), 4 est le moins. Ainsi, b reçoit la valeur provisoire de 4 comme longueur de chemin.

Les longueurs de chemin de A à C sont:

A-c = 5
A-b-c = 4 + 11 = 15

Entre 5, 15, et l'infini (c'était là), 5 est le moins. Ainsi, c reçoit la valeur provisoire de 5 comme longueur de chemin.

B et C étaient les voisins non visités d'un. Actuellement, chacun a une longueur de chemin provisoire. Entre B et C, un sommet doit être choisi contribuer au chemin global final. B et C ont également des voisins.

Les voisins non visitées de B sont D, E et C, avec des longueurs infinies provisoires. Les voisins non visités de C sont B et E avec des longueurs infinies provisoires. Un voisin a un bord direct du sommet en question.

La longueur du chemin calculée de A à D, à B est:

A-b-d = 4 + 9 = 13

La longueur du chemin calculée de A à E, à B est:

A-b-e = 4 + 7 = 11

La longueur du chemin calculée de A à C, à B est:

A-b-c = 4 + 11 = 15

Ce sont les longueurs de chemin à travers les voisins de B à B, du sommet visité, «A». Les longueurs de chemin provisoire à travers C doivent également être déterminées.

La longueur du chemin calculée de A à B, à C est:

A-c-b = 5 + 11 = 16

La longueur du chemin calculée de A à E à C est:

A-c-e = 5 + 3 = 8

Ce sont les longueurs de chemin à travers les voisins de C à C, du sommet visité, «A».

Jusqu'à présent, toutes les longueurs provisoires calculées par des chemins de jeu sont:

A-b-d = 4 + 9 = 13
A-b-e = 4 + 7 = 11
A-b-c = 4 + 11 = 15
A-c-b = 5 + 11 = 16
A-c-e = 5 + 3 = 8

La plus courte de ces longueurs de chemin de rôle est:

A-c-e = 5 + 3 = 8

Ainsi, le sommet, C, est choisi pour la voie à suivre. C'est le prochain sommet visité. Tout chemin possible à travers b est abandonné. C est alors considéré comme visité. Le sommet C est supprimé de la liste non visitée. C est envoyé à la liste visitée (pour être après a).

C devrait avoir des voisins non visités avec des longueurs de chemin provisoire. Dans ce cas, c'est B et E. B a des voisins avec des longueurs de chemin infinies, qui sont d, et e. E a des voisins avec des longueurs de chemin infinies, qui sont d et f. Afin de choisir le prochain nœud visité, les longueurs de chemin de pièce provisoire de C à B et E doivent être calculées. Les calculs sont:

A-c-b-d = 5 + 11 + 9
= 16 + 9 = 25
A-c-b-e = 5 + 11 + 7
= 16 + 7 = 23
A-c-e-d = 5 + 3 + 13
= 8 + 13 = 21
A-c-e-f = 5 + 3 + 6
= 8 + 6 = 14

Le plus court de ces chemins de partie est:

A-c-e-f = 8 + 6 = 14

À ce stade, E est la voie à suivre. C'est le prochain sommet visité. Tout chemin possible à travers D est abandonné. E est supprimé de la liste non visitée et ajouté à la liste visitée (pour être après C).

E a des voisins non visités avec des longueurs de chemin provisoire. Dans ce cas, c'est D et F. Si f avait des voisins non visités, leurs longueurs de chemin provisoire de «A», la source, auraient dû être l'infini. Maintenant, la longueur de f à rien est 0. Afin de choisir le prochain nœud visité (Vertex), les longueurs de chemin de pièce provisoire de E à D et E à F doivent être calculées. Les calculs sont:

A-c-e-d-f = 5 + 3 + 13 + 2
= 8 + 15 = 23
A-c-e-f- = 5 + 3 + 6 + 0
= 14 + 0 = 14

La plus courte de ces longueurs de chemin de rôle est:

A-c-e-f- = 14

À ce stade, F est la voie à suivre. Il est considéré comme visité. F est supprimé de la liste non visitée et ajouté à la liste visitée (pour être après E).

F est la destination. Et donc, la longueur de chemin la plus courte de la source, A, à la destination, F, est 14. Les sommets et leur commande dans la liste visitée devraient être A-C-E-F. C'est le chemin le plus court des sommets. Pour obtenir le chemin le plus court inversé par des sommets, lisez la liste en arrière.

Codage C ++

Le graphique

Le graphique du réseau est un tableau bidimensionnel. C'est:

int g [v] [v] = 0,4,5,0,0,0,
4,0,11,9,7,0,
5,11,0,0,3,0,
0,9,0,0,13,2,
0,7,3,13,0,6,
0,0,0,2,6,0;

Il doit être codé dans la fonction principale C ++. Chaque entrée est la longueur du bord d'un sommet, lecture par rangs, vers le sommet suivant, lecture par colonnes. Une telle valeur n'est pas de plus d'une paire de sommets.

Vertices comme nombres

Pour plus de commodité, les sommets seront identifiés par des nombres, en utilisant le codage ASCII, comme suit:

A est 65
B est 66
C est 67
D est 68
E est 69
F est 70
A est 0 + 65 = 65
B est 1 + 65 = 65
C est 2 + 65 = 65
D est 3 + 65 = 65
E est 4 + 65 = 65
F est 5 + 65 = 65

Les valeurs de codage pour A, B, C, D, E et F sont les suivantes:

A = 0
B = 1
C = 2
D = 3
E = 4
F = 5

65 seront ajoutés à chacun de ces nombres pour obtenir le numéro ASCII correspondant, à partir de laquelle la lettre correspondante sera obtenue.

Début du programme

Le début du programme est:

#inclure
#inclure
Utilisation de Namespace Std;
int int_max = + 2'147'483'647; //infini
#define v 6 // Numéro de sommet en g
int shortestLength = int_max;
vecteur non visité = 0, 1, 2, 3, 4, 5;
VectorVisited;

La valeur de l'infini choisi par le programmeur est 2147483647. Le nombre de sommets, V (en majuscules), est défini (attribué) comme 6. Les éléments du vecteur non visité (tableau) sont a, b, c, d, e et f, comme 0, 1, 2, 3, 4, 5, correspondant aux numéros de code ASCII 65, 66, 67, 68, 69, 70. Cette commande, dans ce cas, n'est pas nécessairement une commande prédéterminée et triée. Les sommets visités seront poussés dans le vecteur visité dans l'ordre découvert par l'algorithme, en commençant par le sommet source.

La fonction getneighbors ()

Cette fonction obtient tous les voisins devant un sommet, à partir de juste après le sommet connexe précédemment visité. Le code de fonction est:

vectorgetneighbors (int graph [v] [v], int Vindx, int prevvisitedIndx)
Vectorneighbors;
pour (int j = prevvisitedIndx + 1; jif (graphique [Vindx] [J] != 0)
voisins.push_back (j);

retour des voisins;

La fonction dijkstra ()

Une fois l'index source (sommet) pris en considération par le programme, la fonction Dijkstra () entre en action de manière récursive jusqu'à ce que l'index de destination (sommet) soit considéré. Le code de fonction est:

void dijkstra (int graph [v] [v], int visiteIdx, int visitLength)
int visitedIndx = visitedx;
int newVisitedIndx = v;
int minLength = int_max;
INT VisitedLength;
int tentlengle1 = 0;
vectorVisitedNbs = getneighbors (graphique, visitedIndx, visitedIdx);
pour (int i = 0; iTentLength1 = VisitLength + Graph [VisitedIdx] [VisitedNbs [i]];
vectorCurrentNBS = getneighbors (graphique, visiténbs [i], visitedx);
if (currentnbs.taille() != 0)
pour (int j = 0; j int tentlengle2 = tentlength1 + graphique [VisitedNbs [i]] [currentnbs [j]];
if (tentlengle2 VisitedLength = Tentlengle1; // confirmé, si finit par être le moins
newVisiteIdIndx = VisitedNbs [i];



autre
VisitedLength = Tentlengle1; //confirmé
newVisiteIdIndx = VisitedNbs [i];


VisitedIndX = newVisitedIdx;
non visité [visitedInDx] = -1;
a visité.push_back (visitedIndX);
ShortStLength = VisitedLength;
if (visitedIndx< V -1)
Dijkstra (graphique, visitedInDx, VisitedLength);

La fonction startDijkstra ()

L'algorithme de Dijkstra commence par cette fonction pour gérer la situation du code source. Le code de fonction est:

void startDijkstra (int graph [v] [v], int srcvidx)
int visitedIndx = srcvidx;
non visité [visitedInDx] = -1;
a visité.push_back (visitedIndX);
int visitedLength = 0;
Dijkstra (graphique, visitedInDx, VisitedLength);

Les segments de code ci-dessus peuvent être assemblés dans l'ordre donné pour former le programme.

La fonction principale C ++

Une fonction principale C ++ appropriée est:

int main (int argc, char ** argv)

int g [v] [v] = 0,4,5,0,0,0,
4,0,11,9,7,0,
5,11,0,0,3,0,
0,9,0,0,13,2,
0,7,3,13,0,6,
0,0,0,2,6,0;
int sourceverTex = 0;
startDijkstra (g, sourceVertex);
couter<pour (int i = 0; icouter<< (char)(visited[i] + 65) << ";
couter<retour 0;

Conclusion

La complexité du temps est le temps de fonctionnement relatif. En supposant que le tri des sommets (voisins) est bon, le programme ci-dessus aurait la complexité du temps suivante:

O ((| e | + | v |) log | v |)

où | e | est le nombre d'arêtes, | V | est le nombre de sommets, et un journal est le journal₂. Le Big-O avec ses supports, () est un moyen d'indiquer que l'expression dans la parenthèse est la complexité du temps (temps de fonctionnement relatif).

La complexité du temps le plus des cas pour l'algorithme de Dijkstra est: O (| V |²)
[/ cc]