Aller au contenu principal

Graphes avancés

#Graphes avancés

Les algorithmes sur les graphes avancés permettent de résoudre des problèmes complexes comme trouver les plus courts chemins, construire des arbres couvrants minimaux, et gérer les flots dans un réseau.

#Plus courts chemins

#Algorithme de Dijkstra

L'algorithme de Dijkstra résout le problème du plus court chemin à partir d'un sommet source dans un graphe pondéré à arêtes positives.

Exemple (Python)

pythonpython
1import heapq2 3def dijkstra(graph, start):4    distances = {node: float('inf') for node in graph}5    distances[start] = 06    pq = [(0, start)]7    8    while pq:9        current_distance, current_node = heapq.heappop(pq)10        11        if current_distance > distances[current_node]:12            continue13            14        for neighbor, weight in graph[current_node].items():


Visualisation


Chargement...


#Algorithme de Bellman-Ford


L'algorithme de Bellman-Ford résout le problème du plus court chemin dans un graphe pondéré, même avec des arêtes de poids négatif. Il peut également détecter les cycles de poids négatif.


Exemple (Python)


pythonpython
1def bellman_ford(graph, start):2    distances = {node: float('inf') for node in graph}3    distances[start] = 04    5    for _ in range(len(graph) - 1):6        for node in graph:7            for neighbor, weight in graph[node].items():8                if distances[node] + weight < distances[neighbor]:9                    distances[neighbor] = distances[node] + weight10                    11    # Vérification des cycles de poids négatif12    for node in graph:13        for neighbor, weight in graph[node].items():14            if distances[node] + weight < distances[neighbor]:




#Arbres couvrants minimaux


#Algorithme de Kruskal


L'algorithme de Kruskal construit un arbre couvrant minimal en triant les arêtes par poids croissant et en les ajoutant une par une, en évitant de créer des cycles.


Exemple (Python)


pythonpython
1class UnionFind:2    def __init__(self, size):3        self.parent = list(range(size))4        self.rank = [0] * size5 6    def find(self, x):7        if self.parent[x] != x:8            self.parent[x] = self.find(self.parent[x])9        return self.parent[x]10 11    def union(self, x, y):12        px, py = self.find(x), self.find(y)13        if px == py:14            return False




#Algorithme de Prim


L'algorithme de Prim construit un arbre couvrant minimal en partant d'un sommet et en ajoutant à chaque étape l'arête de poids minimal reliant un sommet de l'arbre à un sommet hors de l'arbre.


Exemple (Python)


pythonpython
1import heapq2 3def prim(graph, start):4    mst = []5    visited = set([start])6    edges = [(weight, start, to) for to, weight in graph[start].items()]7    heapq.heapify(edges)8    9    while edges:10        weight, frm, to = heapq.heappop(edges)11        if to not in visited:12            visited.add(to)13            mst.append((frm, to, weight))14            for next_to, next_weight in graph[to].items():




#Flots (aperçu)


Les algorithmes de flots permettent de modéliser et résoudre des problèmes de transport dans un réseau, comme l'acheminement de marchandises ou de données. L'algorithme de Ford-Fulkerson est un exemple classique pour trouver le flot maximal dans un réseau.


#Exercice : Algorithme de Floyd-Warshall


Implémentez l'algorithme de Floyd-Warshall pour trouver les plus courts chemins entre toutes les paires de sommets dans un graphe pondéré.


#Instructions


    

  1. Créez une matrice de distances dist où dist[i][j] représente la distance du sommet i au sommet j.
    2. 

  2. Initialisez la matrice avec les poids des arêtes du graphe. Si aucune arête n'existe, utilisez float('inf').
    3. 

  3. Pour chaque sommet k, mettez à jour la matrice en vérifiant si passer par k donne un chemin plus court.
    4. 

  4. La formule de mise à jour est : dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
    5. 



#Exemple de code


pythonpython
1def floyd_warshall(graph):2    V = len(graph)3    dist = [[float('inf')] * V for _ in range(V)]4    5    # Initialisation6    for i in range(V):7        for j in range(V):8            if i == j:9                dist[i][j] = 010            elif graph[i][j] != 0:11                dist[i][j] = graph[i][j]12    13    # Mise à jour14    for k in range(V):




Complexité
    

  • Dijkstra: O((V + E) log V) avec tas de Fibonacci.
    • 

  • Bellman-Ford: O(VE).
    • 

  • Kruskal: O(E log E).
    • 

  • Prim: O(E log V) avec tas binaire.
    • 

  • Floyd-Warshall: O(V^3).
    •