Comment écrire l'algorithme de Bellman-Ford en Python ?

Comment écrire l'algorithme de Bellman-Ford en Python ?

L'algorithme Bellman-Ford est un algorithme permettant de résoudre le problème du chemin le plus court à source unique avec des bords de poids négatifs. Cet article explique comment utiliser Python pour écrire l'algorithme Bellman-Ford et fournit des exemples de code spécifiques.

L'idée principale de l'algorithme Bellman-Ford est d'optimiser le chemin par une itération étape par étape jusqu'à ce que le chemin le plus court soit trouvé. Les étapes de l'algorithme sont les suivantes :

1. Créez un tableau dist[] pour stocker la distance la plus courte entre le point source et les autres sommets.
2. Initialisez tous les éléments du tableau dist[] à l'infini, mais avec une distance de 0 du point source.
3. Par n-1 itérations, pour chaque arête (u, v) :
   1) Si dist[v] > poids(u, v).
4. Vérifiez s'il existe un cycle de poids négatif. Pour chaque arête (u, v) :
   1) Si dist[v] > dist[u] + poids(u, v), il existe un cycle de poids négatif et le chemin le plus court ne peut pas être déterminé.
5. S'il n'y a pas de cycle de poids négatif, le chemin le plus court a été calculé et le tableau dist[] est le chemin le plus court.

Voici un exemple de code de l'algorithme Bellman-Ford écrit en Python :

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def bellman_ford(self, src):
        dist = [float("Inf")] * self.V
        dist[src] = 0

        for _ in range(self.V - 1):
            for u, v, w in self.graph:
                if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

        for u, v, w in self.graph:
            if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                print("图中存在负权环，无法确定最短路径")
                return

        self.print_solution(dist)

    def print_solution(self, dist):
        print("顶点    最短距离")
        for i in range(self.V):
            print(i, "        ", dist[i])

# 示例用法
g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 2, 5)
g.add_edge(3, 1, 1)
g.add_edge(4, 3, -3)
g.bellman_ford(0)

Dans l'exemple ci-dessus, un graphe g est créé et des arêtes sont ajoutées. Appelez ensuite la méthode bellman_ford pour calculer le chemin le plus court et imprimer le résultat. Dans cet exemple, le point source est 0 et le chemin le plus court sera calculé.

La complexité temporelle de l'algorithme de Bellman-Ford est O(V*E), où V est le nombre de sommets et E est le nombre d'arêtes. Dans les applications pratiques, s’il y a un cycle de poids négatif dans le graphique, l’algorithme ne s’arrêtera pas mais entrera dans une boucle infinie. Par conséquent, lorsque vous utilisez l’algorithme Bellman-Ford, vous devez d’abord vérifier s’il existe un cycle de poids négatif.

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!