Algorithme de Dijkstra

Pour écrire le programme, nous avons utilisé la matrice d'adjacence pondérée : aulieu d'avoir des $0$ et des $1$ , on a directement la distance entre les sommets. Si deux sommets ne sont pas reliés, on dit que la distance qui les sépare est infinie, soit

float("inf")

La distance entre un sommet et lui même est $0$ .

Entraînement

Le mieux c'est que tu refasses toi-même l'algo crayon papier sur quelques exemples:

Exemples

Tu peux en profiter pour appliquer au crayon et au papier, le parcours en profondeur et le parcours en largeur.

N'ignore pas ces exercices qui peuvent parraître très simples, car ils te permettent de vraiment bien retenir (et bien comprendre) les algos.

Un autre exercice sur les graphes

Exercice : Modélisation du seuil de percolation sur un réseau hexagonal

image perco

Dans cet exercice, nous allons explorer le concept de percolation sur un graphe représentant un pavage hexagonal en 2D. La percolation est un phénomène probabiliste où des sites (ici, des sommets) sont occupés aléatoirement avec une probabilité $p$ , et l'on s'intéresse à savoir s'il existe un chemin connecté traversant le graphe d'un bord à l'autre (par exemple, du bas vers le haut). Le seuil de percolation est la valeur critique de $p$ au-delà de laquelle une telle connexion devient probable pour de grands réseaux.

Nous modéliserons un graphe sur une grille de taille 12×12 (sommets $(i, j)$ avec $i, j \in \{0, 1, \dots, 11\}$ ). Chaque sommet peut être conducteur (occupé) ou non. Seuls les sommets conducteurs sont connectés à leurs voisins (jusqu'à 6 dans un pavage hexagonal). Le graphe sera représenté par un dictionnaire d'adjacence en Python, où les clés sont les sommets (tuples $(i, j)$ ) et les valeurs sont des listes de voisins conducteurs.

Le pavage hexagonal est défini comme suit :

Chaque sommet $(i, j)$ a des voisins potentiels basés sur sa position.
Pour un sommet intérieur non sur un bord :
- Voisins : droite $(i+1, j)$ , gauche $(i-1, j)$ ,
- Haut : si $j$ est pair, $(i-1, j+1)$ et $(i, j+1)$ ; si $j$ est impair, $(i, j+1)$ et $(i+1, j+1)$ .
- Bas : si $j$ est pair, $(i-1, j-1)$ et $(i, j-1)$ ; si $j$ est impair, $(i, j-1)$ et $(i+1, j-1)$ .
Sur les bords, seuls les voisins valides (dans la grille) sont considérés.
Exemple : Pour $(0, 0)$ conducteur, voisins : $(1, 0)$ et $(0, 1)$ (si conducteurs).

Nous subdiviserons l'exercice en plusieurs questions pour construire progressivement les fonctions nécessaires. Utilisez des structures de base Python (listes, dictionnaires, boucles, conditions) et le module random pour les probabilités.

Question 1 : Générer la liste de tous les sommets

Écrivez une fonction generer_sommets(n) qui prend en paramètre la taille $n$ (ici, $n = 12$ ) et retourne une liste de tous les sommets sous forme de tuples $(i, j)$ avec $0 \leq i, j < n$ .

Exemple d'appel :

sommets = generer_sommets(12)
print(len(sommets))  # Devrait afficher 144

Question 2 : Déterminer les voisins potentiels d'un sommet

Écrivez une fonction voisins_potentiels(sommet, n) qui prend un sommet $(i, j)$ et la taille $n$ , et retourne une liste des voisins potentiels valides (dans la grille), sans considérer s'ils sont conducteurs.

Utilisez les règles du pavage hexagonal décrites ci-dessus.
Vérifiez que chaque voisin potentiel est dans les bornes $[0, n-1] \times [0, n-1]$ .

Exemple :

print(voisins_potentiels((0, 0), 15))  # Devrait retourner [(1, 0), (0, 1)]
print(voisins_potentiels((6, 6), 12))  # Devrait retourner 6 voisins pour un sommet intérieur

Question 3 : Générer les sommets conducteurs

Écrivez une fonction generer_conducteurs(sommets, p) qui prend la liste des sommets et une probabilité $p$ (entre 0 et 1), et retourne un ensemble (set) des sommets conducteurs. Chaque sommet est choisi indépendamment comme conducteur avec probabilité $p$ , en utilisant random.random().

Exemple :

import random
conducteurs = generer_conducteurs(generer_sommets(12), 0.5)
print(len(conducteurs))  # Environ 72 (aléatoire)

Question 4 : Construire le dictionnaire d'adjacence

Écrivez une fonction construire_graphe(conducteurs, n) qui prend l'ensemble des conducteurs et la taille $n$ , et retourne un dictionnaire d'adjacence où :

Les clés sont les sommets conducteurs.
Les valeurs sont des listes de voisins conducteurs (utilisez voisins_potentiels pour filtrer).

Exemple :

graphe = construire_graphe(conducteurs, 12)
print(graphe.get((0, 0), []))  # Liste des voisins conducteurs de (0, 0), si (0, 0) est conducteur

Question 5 : Vérifier la percolation (du bas vers le haut)

Écrivez une fonction percolation_bas_haut(graphe, n) qui vérifie s'il existe un chemin connecté du bas (ligne $j = 0$ ) vers le haut (ligne $j = n-1$ ) dans le graphe.

Utilisez une recherche en largeur (BFS) ou en profondeur (DFS) pour explorer à partir de tous les sommets conducteurs en bas ( $j = 0$ ).
Retournez True si au moins un sommet en haut ( $j = n-1$ ) est atteignable, sinon False.
Utilisez une file (queue) pour BFS, et un ensemble pour les visités.

Exemple d'implémentation esquissée :

from collections import deque 
# "deque" signifie "file" en anglais
# permet d'avoir .popleft() qui n'existe pas par défault sur les listes

def percolation_bas_haut(graphe, n):
    # Sommets de départ : conducteurs avec j=0
    departs = [sommet for sommet in graphe if sommet[1] == 0]
    if not departs:
        return False
    
    visités = set()
    file = deque(departs)
    visités.update(departs)
    
    while file:
        courant = file.popleft()
        if courant[1] == n-1:  # Atteint le haut
            return True
        for voisin in graphe.get(courant, []):
            if voisin not in visités:
                visités.add(voisin)
                file.append(voisin)
    return False

Question bonus : Estimer le seuil de percolation

Écrivez un script principal qui simule 100 fois le processus pour différentes valeurs de $p$ (par exemple, de 0.4 à 0.7 par pas de 0.05), et calcule la proportion de simulations où la percolation ocurre. Affichez les résultats pour estimer le seuil (sur un réseau hexagonal, il est théoriquement autour de 0.5 pour la percolation de sites, mais varie avec la taille).

Exemple de script :

n = 12
simulations = 100
for p in [0.4, 0.45, 0.5, 0.55, 0.6, 0.65, 0.7]:
    succes = 0
    for _ in range(simulations):
        sommets = generer_sommets(n)
        conducteurs = generer_conducteurs(sommets, p)
        graphe = construire_graphe(conducteurs, n)
        if percolation_bas_haut(graphe, n):
            succes += 1
    print(f"Pour p={p}, proportion de percolation : {succes / simulations}")