Tutoriel d'utilisation de l'algorithme SPFA

Champ d'application : il y a des bords de poids négatifs dans un graphique donné. À l'heure actuelle, les algorithmes tels que Dijkstra n'ont pas de place pour être utilisés et la complexité de l'algorithme de Bellman-Ford est trop élevée, donc le SPFA. l'algorithme est utile. Nous convenons qu’il n’y a pas de cycle de poids négatif dans le graphe à pondération dirigée G, c’est-à-dire que le chemin le plus court doit exister. Bien entendu, nous pouvons effectuer un tri topologique avant d’exécuter l’algorithme pour déterminer s’il existe un cycle de poids négatif, mais ce n’est pas l’objet de notre discussion.

Idée d'algorithme : nous utilisons le tableau d pour enregistrer l'estimation du chemin le plus court de chaque nœud et utilisons une liste de contiguïté pour stocker le graphique G. La méthode que nous adoptons est la méthode d'approximation dynamique : mettre en place une file d'attente premier entré, premier sorti pour enregistrer les nœuds à optimiser. Lors de l'optimisation, nous retirons le nœud principal u à chaque fois et utilisons l'estimation actuelle du chemin le plus court de. point u pour quitter le point u. Le nœud pointé v subit une opération de relaxation. Si l'estimation du chemin le plus court du point v est ajustée et que le point v n'est pas dans la file d'attente actuelle, le point v est placé en fin de file d'attente. De cette manière, les nœuds sont continuellement retirés de la file d'attente pour effectuer des opérations de relaxation jusqu'à ce que la file d'attente soit vide

La complexité temporelle attendue est O(ke) , où k est le nombre moyen de fois où tous les sommets entrent dans l'équipe. On peut prouver que k est généralement inférieur ou égal à 2.

Méthode de mise en œuvre :

Créer une file d'attente au départ, il n'y a que le démarrage. point dans la file d'attente, puis créez un tableau pour enregistrer le chemin le plus court du point de départ à tous les points (la valeur initiale du tableau doit être attribuée à la valeur maximale et le chemin du point à lui-même doit être attribué à 0). Effectuez ensuite une opération de relaxation, en utilisant certains points de la file d'attente comme point de départ pour actualiser le chemin le plus court vers tous les points. Si l'actualisation réussit et que le point actualisé n'est pas dans la file d'attente, le point est ajouté à la fin de la file d'attente. . Répétez jusqu'à ce que la file d'attente soit vide.

Déterminer s'il y a une boucle négative :
Si un point entre dans la file d'attente plus de N fois, il y a une boucle négative (SPFA ne peut pas gérer les points négatifs boucles Photo)

Établissez d'abord la distance la plus courte entre le point de départ a et les points restants
Tableau de chemin

                                                                          > 1. Le premier élément (a) de l'équipe est retiré de la file d'attente, et l'opération de relaxation est effectuée sur les points d'extrémité de tous les bords avec a comme point de départ (il y a trois points b, c et d ici). À ce stade, l'état de la table de chemin est :

                                                                                                                                   Cliquez sur
pour vous inscrire la file d'attente. A ce moment, trois nouveaux nœuds b, c, d sont ajoutés à la file d'attente

Le premier élément de l'équipe, le point b, est retiré de la file d'attente. sur les points d'extrémité de toutes les arêtes avec b comme point de départ dans la séquence (il n'y a que le point e ici à ce moment, l'état de la table des chemins est :

   

Dans le tableau du chemin le plus court, l'estimation du chemin le plus court de e est également devenue plus petite e n'existe pas dans la file d'attente, donc e doit également

. rejoindre la file d'attente. À ce moment-là, les éléments de la file d'attente sont c, d, e

L'élément de tête de la file d'attente est retiré de la file d'attente au point c, et les points finaux de tous les bords commençant de c sont séquentiellement détendus (voici e , f deux points), à ce moment l'état de la table de chemin est :

Dans la table du chemin le plus court, E, la valorisation du chemin le plus court de F est devenue plus petite, E existe dans la file d'attente, F n'existe pas. Par conséquent
e n'a pas besoin de rejoindre la file d'attente, et f le fait. À ce stade, les éléments de la file d'attente sont d, e, f

. Le premier élément de l'équipe est le point d Sortez de la file d'attente et effectuez des opérations de relaxation sur les points d'extrémité de toutes les arêtes à partir de d (il n'y a que le point g ici, l'état de la table des chemins est :

                                                                            (La relaxation échoue), aucun nouveau nœud n'entre dans la file d'attente, l'élément dans la file d'attente est f, g

L'élément de tête de l'équipe f pointe hors de la file d'attente, pour toutes les arêtes avec f comme point de départ L'opération de relaxation est effectuée au point final en séquence (il y a sont trois points d, e et g ici). À ce moment, l'état de la table des chemins est :

Dans la table des chemins les plus courts, le Les estimations du chemin le plus court de e et g redeviennent plus petites. Il n'y a pas de point e dans la file d'attente, et e rejoint la file d'attente, et g n'a pas besoin de rejoindre la file d'attente. file d'attente L'élément est g, e

L'élément leader de l'équipe est hors de l'équipe au point g, et l'opération de relaxation est effectuée sur les extrémités de toutes les arêtes avec g comme le point de départ (il n'y a que le point b ici). À ce moment-là, l'état de la table de chemin est :

                                                                               Il n'y a aucun moment où b, b entre dans la file d'attente pour le moment. l'élément dans la file d'attente est e, b

Le premier élément de l'équipe, le point e, quitte la file d'attente et les points finaux de toutes les arêtes avec e comme point de départ sont détendus en séquence ( Il n'y a que le point g ici). À l'heure actuelle, l'état de la table des chemins est :

   

>Dans le tableau du chemin le plus court, l'estimation du chemin le plus court de g n'a pas changé (la relaxation a échoué à ce moment, l'élément dans la file d'attente est b
Le premier élément de la file d'attente est retiré de la file d'attente au point b , effectuez des opérations de relaxation sur les points finaux de toutes les arêtes avec b comme point de départ (il n'y a que le point e ici A ce moment, l'état de la table des chemins est :

    

Dans le tableau du chemin le plus court, l'estimation du chemin le plus court de e n'a pas changé (la relaxation a échoué), et la file d'attente est vide en ce moment

Enfin a arrive Le chemin le plus court de g est 1４

code java

　

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!