Algorithme de chemin le plus court de Bellman-Ford
Étant donné un graphe et un sommet source dans le graphe, trouvez les chemins Les plus courts entre source et tous les sommets dans le graphe donné. Le graphe peut contenir des arêtes de poids négatifs.
L'algorithme de Dijkstra est un algorithme glouton avec une complexité temporelle de O(VLogV) (avec L'utilisation des tas). Dijkstra ne fonctionne pas pour les graphes avec des arêtes de poids négatifs, Bellman-Ford travaille pour de tels graphes.
Bellman-Ford est également plus simple que Dijkstra et convient parfaitement aux systèmes distribués. Mais la complexité temporelle de Bellman-Ford est O(VE), ce qui est plus que Dijkstra.
- initialise les distances de la source à tous les sommets en tant qu'infini et la distance à la source elle-même en tant que 0. Créez un tableau dist[] de taille |V| avec toutes les valeurs infinies sauf dist[src] où src est le sommet source.
- Faire |V|-1 fois où |V| est le nombre de sommets dans le graphe les instructions suivantes.
- Répéter pour chaque arête u-v
- Si dist[v]>dist[u]+poids l'arête u-v, mettez à jour dist[v]=dist[u]+poind de l'arête u-v
- Répéter pour chaque arête u-v
- Si dist[v] > dist [u] + poids de l'arête u-v, alors "le graphe contient un cycle de pondération négatif"
import math class Graphe(): def __init__(self, noeuds): self.matriceAdj = noeuds.copy() def Afficher(self, src, dist): print("les chemins les plus courts allant de ", src, " est : ") for noeud in range(len(self.matriceAdj)): print((noeud+1), "\t", dist[noeud]) def bellmanFord(self, src, ordre): dist = [math.inf] * len(self.matriceAdj) precedence = [-1] * len(self.matriceAdj) dist[src-1] = 0 precedence[src-1] = src-1 relax = True iteration = 0 while (iteration < len(self.matriceAdj)-1) and relax == True: relax = False # relaxation des sommets for elm in ordre: # chaque element elm est un tuple (u,v) if (dist[elm[1]-1] > dist[elm[0]-1]+self.matriceAdj[elm[0]-1][elm[1]-1]): dist[elm[1]-1] = dist[elm[0]-1]+self.matriceAdj[elm[0]-1][elm[1]-1] precedence[elm[1]-1] = elm[0]-1 relax = True iteration += 1 self.Afficher(src, dist) # Test # les sommets sont numérotés à partir de 1 matriceAdj = [[0, 6, 5, 5, 0, 0, 0], [0, 0, 0, 0, -1, 0, 0], [0, -2, 0, 0, 1, 0, 0], [0, 0, -2, 0, 0, -1, 0], [0, 0, 0, 0, 0, 0, 3], [0, 0, 0, 0, 0, 0, 3], [0, 0, 0, 0, 0, 0, 0] ] ordre = [(1, 2), (1, 3), (1, 4), (3, 2), (2, 5), (3, 5), (4, 3), (4, 6), (6, 7), (5, 7)] g = Graphe(matriceAdj) g.bellmanFord(1, ordre)
les chemins les plus courts allant de 1 est : 1 0 2 1 3 3 4 5 5 0 6 4 7 3
Exemple
Partager ce cours avec tes amis :
Rédigé par
ESSADDOUKI
Mostafa