Scribd
Importer
35 vues5 pages

TPA

Le document présente l'algorithme de Ford-Fulkerson pour résoudre le problème de flot maximum dans un graphe. Il décrit les étapes principales de l'algorithme, y compris la représentation du graphe, la recherche de chemins augmentants, le calcul du flot et l'itération jusqu'à l'absence de chemins augmentants. Un exemple de code Python est fourni pour illustrer l'implémentation de l'algorithme.

Transféré par

jacobatouba153
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd
35 vues5 pages

TPA

Le document présente l'algorithme de Ford-Fulkerson pour résoudre le problème de flot maximum dans un graphe. Il décrit les étapes principales de l'algorithme, y compris la représentation du graphe, la recherche de chemins augmentants, le calcul du flot et l'itération jusqu'à l'absence de chemins augmentants. Un exemple de code Python est fourni pour illustrer l'implémentation de l'algorithme.

Transféré par

jacobatouba153
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats DOCX, PDF, TXT ou lisez en ligne sur Scribd

Vous souhaitez implémenter l'algorithme de Ford-Fulkerson pour résoudre le problème de flot

maximum avec le graphe donné. Voici une explication concise et un plan pour le faire en Python :

Étapes principales de l'algorithme

1. Représenter le graphe : Utilisez une matrice d'adjacence ou une liste de dictionnaires pour stocker les
capacités.

2. Recherche d’un chemin augmentant : Utilisez une recherche en profondeur (DFS) ou en largeur (BFS)
pour trouver un chemin dans le graphe résiduel.

3. Calcul du flot : Mettre à jour le flot en augmentant les capacités des arêtes sur le chemin trouvé.

4. Itération : Répétez jusqu’à ce qu’il n’y ait plus de chemin augmentant.

Code Python pour ce graphe

Voici un exemple basé sur le graphe que vous avez fourni :

from collections import defaultdict

# Représentation du graphe avec ses capacités


graph = {

's': {'a': 4, 'e': 9},

'a': {'b': 2, 'c': 3},

'b': {'c': 4, 't': 10},

'c': {'t': 1, 'd': 8},

'd': {'t': 3},

'e': {'d': 8},

# Implémentation de Ford-Fulkerson

class Graph:

def __init__(self, graph):

[Link] = graph

self.residual_graph = defaultdict(dict)

for u in graph:

for v in graph[u]:

self.residual_graph[u][v] = graph[u][v]

def bfs(self, source, sink, parent):

visited = {node: False for node in self.residual_graph}

queue = [source]

visited[source] = True

while queue:

u = [Link](0)
for v, capacity in self.residual_graph[u].items():

if not visited[v] and capacity > 0:

[Link](v)

visited[v] = True

parent[v] = u

if v == sink:

return True

return False

def ford_fulkerson(self, source, sink):

parent = {}

max_flow = 0

while [Link](source, sink, parent):

# Trouver le flot maximum sur le chemin

path_flow = float('Inf')

v = sink

while v != source:

u = parent[v]

path_flow = min(path_flow, self.residual_graph[u][v])

v=u

# Mettre à jour les capacités

v = sink

while v != source:
u = parent[v]

self.residual_graph[u][v] -= path_flow

self.residual_graph[v][u] += path_flow

v=u

max_flow += path_flow

return max_flow

# Exécution de l'algorithme

g = Graph(graph)

source = 's'

sink = 't'

print(f"Le flot maximum est : {g.ford_fulkerson(source, sink)}")

Explication du code

1. Représentation du graphe : Le graphe est stocké dans un dictionnaire avec des capacités.

2. BFS : Trouve les chemins augmentants dans le graphe résiduel.

3. Mise à jour des capacités : Réduit les capacités sur le chemin utilisé et ajoute du flot dans l'autre sens.
4. Flot total : La somme des flots sur les chemins augmentants.

Avec ce code, vous pouvez tester et obtenir le flot maximum pour le graphe fourni.

Vous aimerez peut-être aussi