algorithme du chemin le plus court

Parmi les chemins qui partent d'un sommet et atteignent un autre sommet le long des bords du graphique, le chemin avec la plus petite somme de poids sur chaque bord est appelé le chemin le plus court. Il existe les algorithmes suivants pour résoudre le problème du chemin le plus court, l'algorithme de Dijkstra, l'algorithme de Bellman-Ford, l'algorithme de Floyd et l'algorithme SPFA, etc.

Définition

Le problème du chemin le plus court est un problème d'algorithme classique dans la recherche en théorie des graphes, visant à trouver des graphiques ( Le chemin le plus court entre deux nœuds (composé de nœuds et de chemins). La forme spécifique de l'algorithme comprend :

(1) Le problème de la détermination du chemin le plus court à partir du point de départ - c'est-à-dire le problème de trouver le chemin le plus court lorsque le nœud de départ est connu. Convient pour utiliser l'algorithme de Dijkstra. (Apprentissage recommandé : Tutoriel vidéo PHP)

(2) Le problème de la détermination du chemin le plus court jusqu'au point final - Contrairement au problème de la détermination du point de départ, ce problème est de trouver le chemin le plus court si le nœud final est une question connue. Dans un graphe non orienté, ce problème est tout à fait équivalent au problème de détermination du point de départ. Dans un graphe orienté, ce problème est équivalent au problème de détermination du point de départ en inversant les directions de tous les chemins.

(3) Le problème de déterminer le chemin le plus court entre le point de départ et le point final - c'est-à-dire, étant donné le point de départ et le point final, trouver le chemin le plus court entre les deux nœuds.

(4) Problème global du chemin le plus court - trouvez tous les chemins les plus courts dans le graphique. Convient à l'utilisation de l'algorithme Floyd-Warshall.

Dijkstra

Trouvez le chemin le plus court avec une seule source et sans poids négatif. La rapidité d'exécution est bonne et la complexité temporelle est O(V*V+E). Si le point source est accessible, O(V*lgV+E*lgV) =>O(E*lgV).
Quand il s'agit d'un graphe clairsemé, à ce moment E=V*V/lgV, donc la complexité temporelle de l'algorithme peut être O(V^2). Si le tas de Fibonacci est utilisé comme file d'attente prioritaire, la complexité temporelle de l'algorithme est O(V*lgV + E).

Floyd

Trouvez le chemin le plus court avec plusieurs sources et sans bords de poids négatifs. Utilisez une matrice pour enregistrer le graphique. La rapidité est mauvaise et la complexité temporelle est O(V^3).
L'algorithme de Floyd-Warshall (algorithme de Floyd-Warshall) est un algorithme permettant de résoudre le chemin le plus court entre deux points quelconques. Il peut gérer correctement le problème du chemin le plus court d'un graphe orienté ou d'un poids négatif.

Bellman-Ford

Pour trouver le chemin le plus court à partir d'une seule source, vous pouvez déterminer s'il existe une boucle de poids négative (s'il y en a, alors il n'y en a pas chemin le plus court),
actualité Mieux, complexité temporelle O(VE).

L'algorithme de Bellman-Ford est un algorithme permettant de résoudre le problème du chemin le plus court à source unique.

SPFA

est l'optimisation de file d'attente de Bellman-Ford, qui a une rapidité relativement bonne et une complexité temporelle de O(kE). (k≪≪V).

Semblable à l'algorithme de Bellman-ford, l'algorithme SPFA utilise une série d'opérations de relaxation pour obtenir le chemin le plus court d'un nœud à tous les autres nœuds du graphique. La différence est que l'algorithme SPFA maintient une file d'attente de sorte qu'une fois le chemin le plus court actuel d'un nœud mis à jour, il n'est pas nécessaire de mettre à jour immédiatement les autres nœuds, réduisant ainsi considérablement le nombre d'opérations répétées.

Pour plus d'articles techniques liés à PHP, veuillez visiter la colonne Tutoriel graphique PHP pour apprendre !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!