algorithm
Algorithme Bellman – Ford

Remarques

Algorithme du chemin le plus court à source unique (étant donné qu'il y a un cycle négatif dans un graphique)

Avant de lire cet exemple, il est nécessaire d'avoir une brève idée de la relaxation des contours. Vous pouvez l'apprendre d' ici

Algorithme Bellman-Ford calcule les chemins les plus courts d'un sommet source unique vers tous les autres sommets d'un digraphe pondéré. Même s'il est plus lent que l'algorithme de Dijkstra , il fonctionne dans les cas où le poids de l'arête est négatif et qu'il détecte également un cycle de pondération négatif dans le graphique. Le problème avec l'algorithme de Dijkstra est que s'il y a un cycle négatif, vous continuez à parcourir le cycle encore et encore et continuez à réduire la distance entre deux sommets.

L'idée de cet algorithme est de parcourir tous les bords de ce graphe un par un dans un ordre aléatoire. Cela peut être n'importe quel ordre aléatoire. Mais vous devez vous assurer que si uv (où u et v sont deux sommets dans un graphique) est l’un de vos ordres, alors il doit y avoir un bord de u à v . Habituellement, il est pris directement dans l'ordre des entrées données. Encore une fois, tout ordre aléatoire fonctionnera.

Après avoir sélectionné la commande, nous détendrons les bords selon la formule de relaxation. Pour une arête uv donnée vont de u à v de la formule de relaxation est la suivante :

if distance[u] + cost[u][v] < d[v]
    d[v] = d[u] + cost[u][v]

Autrement dit, si la distance de la source à un sommet u + le poids du bord uv est inférieur à la distance entre la source et un autre sommet v , nous mettons à jour la distance de la source à v . Nous devons assouplir les arêtes au maximum (V-1) fois où V est le nombre d'arêtes du graphique. Pourquoi (V-1) vous demandez? Nous allons l'expliquer dans un autre exemple. Nous allons également garder une trace du sommet parent de tout sommet, c'est-à-dire que lorsque nous relâchons un bord, nous allons définir:

parent[v] = u

Cela signifie que nous avons trouvé un autre chemin plus court pour atteindre v via u . Nous aurons besoin de cela plus tard pour imprimer le plus court chemin de la source au sommet de destination.

Regardons un exemple. Nous avons un graphique:

Nous avons sélectionné 1 comme sommet source . Nous voulons trouver le plus court chemin de la source à tous les autres sommets.

Au début, d [1] = 0 car c'est la source. Et le repos est infini , car nous ne connaissons pas encore leur distance.

Nous allons assouplir les bords dans cette séquence:

+--------+--------+--------+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |    4   |    5   |    6   |
+--------+--------+--------+--------+--------+--------+--------+
|  Edge  |  4->5  |  3->4  |  1->3  |  1->4  |  4->6  |  2->3  |
+--------+--------+--------+--------+--------+--------+--------+

Vous pouvez prendre n'importe quelle séquence que vous voulez. Si nous détendons les bords une fois, qu'est-ce que nous obtenons? Nous obtenons la distance entre la source et tous les autres sommets du chemin qui utilise au maximum 1 front. Détendons maintenant les arêtes et mettons à jour les valeurs de d [] . On a:

1. d [4] + coût [4] [5] = infini + 7 = infini . Nous ne pouvons pas mettre à jour celui-ci.
2. d [2] + coût [3] [4] = infini . Nous ne pouvons pas mettre à jour celui-ci.
3. d [1] + coût [1] [2] = 0 + 2 = 2 < d [2] . Donc d [2] = 2 . Aussi parent [2] = 1 .
4. d [1] + coût [1] [4] = 4 . Donc d [4] = 4 < d [4] . parent [4] = 1 .
5. d [4] + coût [4] [6] = 9 . d [6] = 9 < d [6] . parent [6] = 4 .
6. d [2] + coût [2] [2] = infini . Nous ne pouvons pas mettre à jour celui-ci.

Nous n'avons pas pu mettre à jour certains sommets, car la condition d[u] + cost[u][v] < d[v] ne correspondait pas. Comme nous l'avons déjà dit, nous avons trouvé les chemins de la source vers les autres nœuds en utilisant un maximum de 1 front.

Notre deuxième itération nous fournira le chemin en utilisant 2 nœuds. On a:

1. d [4] + coût [4] [5] = 12 < d [5] . d [5] = 12 . parent [5] = 4 .
2. d [3] + coût [3] [4] = 1 < d [4] . d [4] = 1 . parent [4] = 3 .
3. d [3] reste inchangé.
4. d [4] reste inchangé.
5. d [4] + coût [4] [6] = 6 < d [6] . d [6] = 6 . parent [6] = 4 .
6. d [3] reste inchangé.

Notre graphique ressemblera à:

Notre 3ème itération ne mettra à jour que le sommet 5 , où d [5] sera 8 . Notre graphique ressemblera à:

Après cela, peu importe le nombre d'itérations que nous faisons, nous aurons les mêmes distances. Nous allons donc garder un drapeau qui vérifie si une mise à jour a lieu ou non. Si ce n'est pas le cas, nous allons simplement casser la boucle. Notre pseudo-code sera:

Procedure Bellman-Ford(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
    parent[i] := NULL
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            parent[v] := u
            flag := true
        end if
    end for
    if flag == false
        break
end for
Return d

Pour suivre le cycle négatif, nous pouvons modifier notre code en utilisant la procédure décrite ici . Notre pseudo-code complété sera:

Procedure Bellman-Ford-With-Negative-Cycle-Detection(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
    parent[i] := NULL
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            parent[v] := u
            flag := true
        end if
    end for
    if flag == false
        break
end for
for all edges from (u,v) in Graph
    if d[u] + cost[u][v] < d[v]
        Return "Negative Cycle Detected"
    end if
end for
Return d

Chemin d'impression:

Pour imprimer le plus court chemin vers un sommet, nous reviendrons à son parent jusqu'à ce que nous trouvions NULL , puis imprimons les sommets. Le pseudo-code sera:

Procedure PathPrinting(u)
v := parent[u]
if v == NULL
    return
PathPrinting(v)
print -> u

Complexité:

Puisque nous devons assouplir les arêtes maximales (V-1) , la complexité temporelle de cet algorithme sera égale à O (V * E) où E représente le nombre d'arêtes, si nous utilisons la adjacency list pour représenter le graphique. Cependant, si la adjacency matrix est utilisée pour représenter le graphique, la complexité temporelle sera O (V ^ 3) . La raison est que nous pouvons parcourir tous les fronts dans le temps O (E) lorsque la adjacency list est utilisée, mais cela prend du temps O (V ^ 2) lorsque la adjacency matrix est utilisée.

Pourquoi avons-nous besoin de détendre tous les bords au maximum (V-1) fois

Pour comprendre cet exemple, il est recommandé d'avoir une idée succincte de l'algorithme de chemin le plus court à source unique de Bellman-Ford, disponible ici

Dans l'algorithme Bellman-Ford, pour trouver le chemin le plus court, nous devons assouplir tous les bords du graphique. Ce processus est répété au maximum (V-1) fois, où V est le nombre de sommets dans le graphique.

Le nombre d'itérations nécessaires pour trouver le plus court chemin de la source à tous les autres sommets dépend de l'ordre que nous choisissons pour assouplir les bords.

Regardons un exemple:

Ici, le sommet source est 1. Nous allons trouver la plus courte distance entre la source et tous les autres sommets. Nous pouvons clairement voir que, pour atteindre le sommet 4 , dans le pire des cas, cela prendra des arêtes (V-1) . Maintenant, en fonction de l'ordre dans lequel les arêtes sont découvertes, il faut parfois (V-1) fois pour découvrir le sommet 4 . Vous n'avez pas compris? Utilisons l'algorithme de Bellman-Ford pour trouver le chemin le plus court ici:

Nous allons utiliser cette séquence:

+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |
+--------+--------+--------+--------+
|  Edge  |  3->4  |  2->3  |  1->2  |
+--------+--------+--------+--------+

Pour notre première itération:

1. d [3] + coût [3] [4] = infini . Cela ne changera rien.
2. d [2] + coût [2] [3] = infini . Cela ne changera rien.
3. d [1] + coût [1] [2] = 2 < d [2] . d [2] = 2 . parent [2] = 1 .

Nous pouvons voir que notre processus de relaxation n'a changé que d [2] . Notre graphique ressemblera à:

Deuxième itération:

1. d [3] + coût [3] [4] = infini . Cela ne changera rien.
2. d [2] + coût [2] [3] = 5 < d [3] . d [3] = 5 . parent [3] = 2.
3. Il ne sera pas changé.

Cette fois, le processus de relaxation a changé d [3] . Notre graphique ressemblera à:

Troisième itération:

1. d [3] + coût [3] [4] = 7 < d [4] . d [4] = 7 . parent [4] = 3 .
2. Il ne sera pas changé.
3. Il ne sera pas changé.

Notre troisième itération a finalement trouvé le plus court chemin vers 4 à partir de 1 . Notre graphique ressemblera à:

Donc, il a fallu 3 itérations pour trouver le chemin le plus court. Après celui-ci, peu importe le nombre de fois où nous relâchons les bords, les valeurs de d [] resteront les mêmes. Maintenant, si nous considérions une autre séquence:

+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |
+--------+--------+--------+--------+
|  Edge  |  1->2  |  2->3  |  3->4  |
+--------+--------+--------+--------+

Nous aurions:

1. d [1] + coût [1] [2] = 2 < d [2] . d [2] = 2 .
2. d [2] + coût [2] [3] = 5 < d [3] . d [3] = 5 .
3. d [3] + coût [3] [4] = 7 < d [4] . d [4] = 5 .

Notre toute première itération a trouvé le chemin le plus court entre la source et tous les autres nœuds. Une autre séquence 1-> 2 , 3-> 4 , 2-> 3 est possible, ce qui nous donnera le plus court chemin après 2 itérations. Nous pouvons décider que peu importe la manière dont nous organisons la séquence, il ne faudra pas plus de 3 itérations pour trouver le plus court chemin à partir de la source dans cet exemple.

Nous pouvons conclure que, dans le meilleur des cas, il faudra 1 itération pour trouver le plus court chemin depuis la source . Dans le pire des cas, il faudra des itérations (V-1) , c'est pourquoi nous répétons le processus de relaxation (V-1) .

Détection d'un cycle négatif dans un graphique

Pour comprendre cet exemple, il est recommandé d'avoir une brève idée de l'algorithme de Bellman-Ford, disponible ici

En utilisant l'algorithme de Bellman-Ford, nous pouvons détecter s'il y a un cycle négatif dans notre graphique. Nous savons que pour trouver le chemin le plus court, nous devons assouplir toutes les arêtes du graphe (V-1) , où V est le nombre de sommets d'un graphe. Nous avons déjà vu que dans cet exemple , après les itérations (V-1) , nous ne pouvons pas mettre à jour d [] , peu importe le nombre d'itérations que nous faisons. Ou pouvons-nous?

S'il y a un cycle négatif dans un graphique, même après des itérations (V-1) , nous pouvons mettre à jour d [] . Cela se produit car pour chaque itération, le parcours du cycle négatif diminue toujours le coût du chemin le plus court. C'est pourquoi l'algorithme Bellman-Ford limite le nombre d'itérations à (V-1) . Si nous utilisions l'algorithme de Dijkstra ici, nous serions coincés dans une boucle sans fin. Cependant, concentrons-nous sur la recherche de cycle négatif.

Supposons que nous ayons un graphique:

Prenons le sommet 1 comme source . Après avoir appliqué l'algorithme de chemin le plus court à source unique de Bellman-Ford au graphique, nous découvrirons les distances entre la source et tous les autres sommets.

Voici comment le graphique se présente après (V-1) = 3 itérations. Ce devrait être le résultat car il y a 4 arêtes, nous avons besoin d'au plus 3 itérations pour trouver le plus court chemin. Donc, soit c'est la réponse, soit il y a un cycle de pondération négatif dans le graphique. Pour trouver que, après les itérations (V-1) , nous effectuons une dernière itération finale et que si la distance continue à diminuer, cela signifie qu'il y a définitivement un cycle de pondération négatif dans le graphique.

Pour cet exemple: si on vérifie 2-3 , d [2] + cost [2] [3] nous donnera 1 qui est inférieur à d [3] . On peut donc en conclure qu'il y a un cycle négatif dans notre graphique.

Alors, comment découvrons-nous le cycle négatif? Nous modifions un peu la procédure Bellman-Ford:

Procedure NegativeCycleDetector(Graph, source):
n := number of vertices in Graph
for i from 1 to n
    d[i] := infinity
end for
d[source] := 0
for i from 1 to n-1
    flag := false
    for all edges from (u,v) in Graph
        if d[u] + cost[u][v] < d[v]
            d[v] := d[u] + cost[u][v]
            flag := true
        end if
    end for
    if flag == false
        break
end for
for all edges from (u,v) in Graph
    if d[u] + cost[u][v] < d[v]
        Return "Negative Cycle Detected"
    end if
end for
Return "No Negative Cycle"

C'est ainsi que nous découvrons s'il y a un cycle négatif dans un graphique. Nous pouvons également modifier l'algorithme Bellman-Ford pour suivre les cycles négatifs.