En mathématiques et en informatique, il y aune zone distincte appelée théorie des graphes. Dans son cadre, divers problèmes sont posés et résolus, par exemple pour trouver le chemin le plus court entre les pics. L'algorithme de Dijkstra est depuis longtemps l'un des moyens les plus courants de résoudre ce problème chez les mathématiciens.
On pense que le concept de graphique a été introduit dansutilisé au XVIIIe siècle par Leonard Euler. C'est lui qui a annoncé la formulation et la solution de l'un des problèmes classiques de cette théorie - sur les sept ponts de Koenigsberg. Afin d'expliquer l'objet de cette théorie, ils utilisent le plus souvent une telle analogie comme mouvement entre différentes villes. Ensuite, le graphique sur le plan représentera l'ensemble du schéma d'itinéraire, où les sommets seront des points spécifiques (par exemple, des villes), et les bords seront des chemins d'un sommet à un autre (un analogue d'une route entre les villes). L'algorithme de Dijkstra, en plus d'autres méthodes, peut apporter une solution à cette question.
L'un des problèmes standard de la théorie des graphes estcelui dans lequel vous devez déterminer le chemin rentable entre deux points. Elle peut être réduite sur un plan à la solution d'un graphe dans lequel les sommets - les villes - sont reliés par des arêtes, qui sont des routes possibles. De plus, chaque route a sa propre longueur, par conséquent, certains fonds devront être dépensés pour voyager le long de celle-ci. Cette somme équivaut au poids d'une arête sur le graphique. Ensuite, le problème dans la pratique peut être formulé comme suit: comment ouvrir la voie d'une ville à une autre afin de dépenser un minimum d'argent sur la route.
Des solutions
Pour résoudre ce problème, certainsalgorithmes qui sont devenus largement connus dans le monde scientifique. Par exemple, l'algorithme Floyd-Warshall, Ford-Bellman. L'algorithme de Dijkstra est également un moyen classique de trouver une solution. Il peut être utilisé à la fois pour un graphique pondéré (nous connaissons le poids de chaque arête) et un graphique clairsemé. Pour trouver le chemin final, vous devez suivre plusieurs étapes.
Algorithme de Dijkstra
La signification de cette méthode est quetous les sommets sont traversés, en commençant par un point donné, et chacun reçoit une étiquette avec une certaine valeur. Ensuite, le résultat inclura les sommets dont les étiquettes sont minimales. Lors de la première étape, le sommet d'origine reçoit une étiquette avec la valeur 0. Ensuite, tous les sommets suivants sont considérés, c'est-à-dire ceux qui peuvent être atteints à partir de l'original. Des étiquettes leur sont attribuées, dont la valeur est déterminée comme la somme du poids de la source et du chemin. A partir des sommets de l'étape suivante, celui avec la plus petite valeur d'étiquette est sélectionné, et tous les sommets sont étudiés qui peuvent être atteints à partir de celui-ci sans utiliser de sommets intermédiaires. Une nouvelle valeur d'étiquette est déterminée, égale à l'étiquette du sommet source plus le poids du chemin. Si la valeur reçue est inférieure à l'étiquette du sommet, l'étiquette est modifiée. Sinon, la valeur d'origine reste. Dans ce cas, dans un tableau séparé, dont la dimension est égale au nombre de sommets du graphe, le résultat de l'optimisation est enregistré, par lequel le chemin est déterminé. Pour implémenter une méthode comme l'algorithme de Dijkstra, Pascal propose des outils très pratiques. L'algorithme a l'avantage de pouvoir être facilement utilisé comme base pour un programme de petite taille. Des exemples de tels produits logiciels sont faciles à trouver sur Internet.
