Plus courts chemins entre toutes les paires de sommets dans un graphe orienté et pondéré - Floyd-Warshall

Plus courts chemins entre toutes les paires de sommets dans un graphe orienté et pondéré - Floyd-Warshall

L'algorithme de Floyd Warshall permet de résoudre le problème du chemin le plus court pour toutes les paires de sommets dans un graphe orienté pondéré.

Dans un premier temps, nous initialisons la matrice de solution, identique à celle du graphe d'entrée.
Ensuite, nous mettons à jour la matrice de solution en considérant tous les sommets comme un sommet intermédiaire.
L'idée est de sélectionner un à un tous les sommets et de mettre à jour tous les chemins les plus courts incluant le sommet sélectionné en tant que sommet intermédiaire du chemin le plus court.
Lorsque nous choisissons le nombre de sommets comme sommet intermédiaire, nous avons déjà considéré les sommets {0, 1, 2, .. k-1} comme des sommets intermédiaires.
Pour chaque paire (i, j) des sommets source et destination, respectivement, il existe deux cas possibles.

  1. k n'est pas un sommet intermédiaire sur le chemin le plus court de i à j. Nous gardons la valeur de dist[i][j] telle qu'elle est.
  2. k est un sommet intermédiaire dans le plus court chemin de i à j. Nous mettre à jour la valeur de dist[i][j] par dist[i][k]+dist[k][j] si dist[i][j] > dist[i][k] + dist[k][j]
                    import math

                    class Graphe():
                    
                        def __init__(self, noeuds):
                            self.matriceAdj = noeuds.copy()
                    
                        def Afficher(self, res):
                            print("les chemins les plus courts allant de  est : ")
                            n = len(res)
                            for i in range(n):
                                print("les chemins les plus courts allant de ", i+1, " est : ")
                                for j in range(n):
                                    print(res[i][j], end=" ")
                                print("")
                    
                        def FloydWarshal(self):
                            res = self.matriceAdj.copy()
                            n = len(self.matriceAdj)
                    
                            for k in range(n):
                                for i in range(n):
                                    for j in range(n):
                                        res[i][j] = min(res[i][j], res[i][k]+res[k][j])
                    
                            self.Afficher(res)
                    
                    
                    # Test
                    matriceAdj = [[0, 3, math.inf, 7],
                                  [8, 0, 2, math.inf],
                                  [5, math.inf, 0, 1],
                                  [2, math.inf, math.inf, 0],
                                  ]
                    g = Graphe(matriceAdj)
                    g.FloydWarshal()
                    
            
                les chemins les plus courts allant de  1  est :
                0 3 5 6 
                les chemins les plus courts allant de  2  est :
                5 0 2 3 
                les chemins les plus courts allant de  3  est :
                3 6 0 1 
                les chemins les plus courts allant de  4  est :
                2 5 7 0
            

Exemple

Rédigé par M. ESSADDOUKI

Many people realize their hearts desires late in life. Continue learning, never stop striving and keep your curiosity sharp, and you will never become too old to appreciate life.