# import sys
# sys.path.append('../../../../Latex/')
# from commandes_python import *
from collections import deque
import numpy as np
import matplotlib.pyplot as pl
# import numpy as np
## Appli 4
1.2. : Décompte du nombre de chemins¶
Soit $M^{n}$ la puissance usuelle $n$-ième (avec $n>1$) de la matrice d'adjacence $M$ d'un graphe $(S, A)$. Alors le coefficient $m_{i, j}^{(n)}$ de $M^{n}$ contient le nombre de chemins distincts de longueur $n$ du $i$-ième sommet du graphe au $j$-ième sommet du graphe.
Démonstration
Effectuons une récurrence sur $k$ : $$ m_{i, j}^{(1)}=m_{i, j} $$ désigne bien le nombre de chemins allant de $x_{i}$ à $x_{j}$ (où $i$ et $j$ peuvent être égaux). Supposons le résultat vrai pour l'entier $k-1$, avec $k \geq 1$.
Comme: $$ M^{k}=M^{k-1} M $$ nous avons par construction de la multiplication matricielle : $$ m_{i, j}^{(k)}=\sum_{\ell=1}^{n} m_{i \ell}^{(k-1)} m_{\ell, j} $$ Par hypothèse de récurrence, $m_{i,\ell}^{(k-1)}$ est le nombre de chemins de longueur $k-1$ allant de $x_{i}$ à $x_{\ell}$ et $m_{\ell, j}$ est par construction le nombre de chemins de longueur $1$ allant de $x_{\ell}$ à $x_{j}$. En particulier il est égal à 1 si $\left(x_{i}, x_{j}\right)$ est une arête du graphe et 0 sinon.
Donc le produit $ m_{i,\ell}^{(k-1)} m_{l, j} $ donne pour une valeur de $\ell$ donnée le nombre de chemins de longueur $k$ allant de $x_i$ à $x_j$ dont la dernière arête est $\left( x_{\ell},x_j \right)$. La somme: $$ \sum_{\ell=1}^{n} m_{i \ell}^{(k-1)} m_{\ell, j} $$ donne donc toutes les possibilités (chemins) de longueur $k$ allant de $x_{i}$ à $x_{j}$ quel que soit le point de début de la dernière arête.
Appli ITC2.4 : Décompte de chemins¶
On définit ici la matrice d'adjacence associée au graphe de l'application ITC2.3
M0=np.array([[0,1,1,0,0],[1,0,0,0,1],[1,0,0,1,1],[0,0,1,0,0],[0,1,1,0,0]])
M0
array([[0, 1, 1, 0, 0], [1, 0, 0, 0, 1], [1, 0, 0, 1, 1], [0, 0, 1, 0, 0], [0, 1, 1, 0, 0]])
Pour trouver le nombre de chemins de longueur 2, on peut élever au carré la matrice précédente
M2=np.dot(M0,M0)
M2
array([[2, 0, 0, 1, 2], [0, 2, 2, 0, 0], [0, 2, 3, 0, 0], [1, 0, 0, 1, 1], [2, 0, 0, 1, 2]])
Le nombre de chemin de longueur 2 reliant 2 à 0 est donc M2[2,0]
M2[2,0]
0
On procède de même pour les chemins de longueur 3.
M3=np.dot(M2,M0)
print(M3)
print(M3[2,0])
[[0 4 5 0 0] [4 0 0 2 4] [5 0 0 3 5] [0 2 3 0 0] [0 4 5 0 0]] 5
2.1. Utilisation du module deque¶
help(deque.append)
help(deque.appendleft)
help(deque.pop)
help(deque.popleft)
Help on method_descriptor: append(...) Add an element to the right side of the deque. Help on method_descriptor: appendleft(...) Add an element to the left side of the deque. Help on method_descriptor: pop(...) Remove and return the rightmost element. Help on method_descriptor: popleft(...) Remove and return the leftmost element.
Association d'une matrice d'adjacence Mex
au graphe suivant :¶
Mex=[[0,1,1,0,0,0],[1,0,0,0,0,1],[1,0,0,1,0,0],[0,0,1,0,1,0],[0,0,0,1,0,0],[1,0,0,0,0,0]]
# la même matrice mais en supprimant l'arête 1<->5
Mex2=[[0,1,1,0,0,0],[1,0,0,0,0,0],[1,0,0,1,0,0],[0,0,1,0,1,0],[0,0,0,1,0,0],[0,0,0,0,0,0]]
2.2. Parcours en profondeur¶
Le but est d’afficher tous les sommets d’un graphe représenté par une matrice d’adjacence M (codée par une liste de listes) en partant d’un sommet arbitraire (on considère que les 𝑛 sommets du graphe sont les entiers 0, … , 𝑛 − 1 ; l’utilisation d’un dictionnaire permet de facilement se rapporter à ce cas).
def parcours_profondeur(M,s0):
"""
M: matrice d'adjacence sous forme d'une liste de listes
s0: sommet de départ
sortie: aucune
affiche tous les sommets de M, en partant du sommet s0
"""
n=len(M)
pile_sommets_en_attente=deque([s0])
liste_sommets_vus={i:0 for i in range(n)}
while len(pile_sommets_en_attente)>0:
s=pile_sommets_en_attente.popleft()
if liste_sommets_vus[s]==0:
print(s)
liste_sommets_vus[s]=1
j=0
while j<n:
if M[s][j] and liste_sommets_vus[j]==0:
pile_sommets_en_attente.appendleft(j)
print(pile_sommets_en_attente,liste_sommets_vus)
j+=1
parcours_profondeur(Mex,2)
2 deque([0]) {0: 0, 1: 0, 2: 1, 3: 0, 4: 0, 5: 0} deque([3, 0]) {0: 0, 1: 0, 2: 1, 3: 0, 4: 0, 5: 0} 3 deque([4, 0]) {0: 0, 1: 0, 2: 1, 3: 1, 4: 0, 5: 0} 4 0 deque([1]) {0: 1, 1: 0, 2: 1, 3: 1, 4: 1, 5: 0} 1 deque([5]) {0: 1, 1: 1, 2: 1, 3: 1, 4: 1, 5: 0} 5
2.3. Parcours en largeur¶
def parcours_largeur(M,s0):
"""
M: matrice d'adjacence sous forme d'une liste de listes
s: sommet de départ
sortie: aucune
affiche tous les sommets de M, en partant du sommet i
"""
n=len(M)
file_sommets_en_attente=deque([s0])
liste_sommets_vus={i:0 for i in range(n)}
while len(file_sommets_en_attente)>0:
s=file_sommets_en_attente.popleft()
if liste_sommets_vus[s]==0:
print(s)
liste_sommets_vus[s]=1
j=0
while j<n:
if M[s][j] and liste_sommets_vus[j]==0:
file_sommets_en_attente.append(j)
print(file_sommets_en_attente,liste_sommets_vus)
j+=1
parcours_largeur(Mex,2)
2 deque([0]) {0: 0, 1: 0, 2: 1, 3: 0, 4: 0, 5: 0} deque([0, 3]) {0: 0, 1: 0, 2: 1, 3: 0, 4: 0, 5: 0} 0 deque([3, 1]) {0: 1, 1: 0, 2: 1, 3: 0, 4: 0, 5: 0} 3 deque([1, 4]) {0: 1, 1: 0, 2: 1, 3: 1, 4: 0, 5: 0} 1 deque([4, 5]) {0: 1, 1: 1, 2: 1, 3: 1, 4: 0, 5: 0} 4 5
3.2. Minimisation étapes¶
Minimiser le nombre d'étapes pour aller d'un point $A$ à un point $B$ est une légère variation du parcours en largeur mené précédemment : il suffit de tester pour chaque sommet rencontré si c'est celui que l'on recherche.
Cette première version du code se contente de tester si un chemin existe entre deux sommets passés en arguments.
def minimise_etapes(M,s_a,s_b):
"""
M: matrice d'adjacence sous forme d'une liste de listes
s_a: sommet de départ
s_b: sommet d'arrivée
sortie: b$\infty$l. qui détermine si un chemin existe de A à B
"""
n=len(M)
file_sommets_en_attente=deque([s_a])
liste_sommets_vus={i:0 for i in range(n)}
while len(file_sommets_en_attente)>0:
s=file_sommets_en_attente.popleft()
liste_sommets_vus[s]=1
if s==s_b:
return True
for j in range(n):
if M[s][j] and liste_sommets_vus[j]==0:
file_sommets_en_attente.append(j)
return False
minimise_etapes(M0,0,4)
True
Cette seconde version retourne en plus le nombre d'étapes minimal entre les deux sommets testés.
def minimise_etapes_compte(M,s_a,s_b):
"""
M: matrice d'adjacence sous forme d'une liste de listes
s_a: sommet de départ
s_b: sommet d'arrivée
sortie: nombre d'étapes pour aller de A à B
"""
assert minimise_etapes(M,s_a,s_b)
n=len(M)
file_sommets_en_attente=deque([s_a])
liste_sommets_vus={i:0 for i in range(n)}
poids_sommets={i:0 for i in range(n)}
poids_sommets[s_a]=0
while len(file_sommets_en_attente)>0:
s=file_sommets_en_attente.popleft()
liste_sommets_vus[s]=1
if s==s_b:
return poids_sommets[s]
for j in range(n):
if M[s][j] and liste_sommets_vus[j]==0:
file_sommets_en_attente.append(j)
poids_sommets[j]=poids_sommets[s]+1
minimise_etapes_compte(M0,0,4)
2
3.3. Algorithme de Dijkstra¶
Appli ITC2.6¶
Le tableau rempli est le suivant
Étape | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
0 | 0 | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
1 | 0 | 3 | 4 | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
2 | 0 | 3 | 4 | 8 | $\infty$ | 14 | $\infty$ |
3 | 0 | 3 | 4 | 7 | 19 | 14 | $\infty$ |
4 | 0 | 3 | 4 | 7 | 17 | 14 | $\infty$ |
5 | 0 | 3 | 4 | 7 | 17 | 14 | 27 |
6 | 0 | 3 | 4 | 7 | 17 | 14 | 27 |
Version simple¶
Le programme retourne le nombre minimal de sommets qui sépare les sommets A et B.
def dijkstra(M,s_a,s_b):
"""
M: matrice d'adjacence pondérée (liste de listes)
s_a: sommet de départ
s_b: sommet d'arrivée
sortie: coût minimal pour aller de s_a à s_b
"""
assert minimise_etapes(M,s_a,s_b)
n=len(M)
poids_sommets={i:float('inf') for i in range(n)}
dic_sommets_minimises={i:0 for i in range(n)}
s,poids_sommets[s_a],dic_sommets_minimises[s_a]=s_a,0,1
while dic_sommets_minimises[s_b]==0:
# traitement du sommet: maj des poids des voisins
for j in range(n):
# seuls les voisins non optimises sont traités
if M[s][j] and dic_sommets_minimises[j]==0:
if poids_sommets[s]+M[s][j]<poids_sommets[j]:
poids_sommets[j]=poids_sommets[s]+M[s][j]
# choix du prochain sommet: min des poids restants
poids_min=float('inf')
for j in range(n):
if dic_sommets_minimises[j]==0 and poids_sommets[j]<poids_min:
s_min,poids_min=j,poids_sommets[j]
dic_sommets_minimises[s_min]=1
s=s_min
# print(s,poids_sommets,dic_sommets_minimises)
return poids_sommets[s_b]
Version avec chemin¶
Le code précédent est modifié pour retourner la liste des sommets parcourus pour aller des sommets A et B.
def dijkstra_chemin(M,s_a,s_b):
"""
M: matrice d'adjacence pondérée (liste de listes)
s_a: sommet de départ
s_b: sommet d'arrivée
sortie: coût minimal pour aller de s_a à s_b,chemin suivi
"""
assert minimise_etapes(M,s_a,s_b)
n=len(M)
poids_sommets={i:float('inf') for i in range(n)}
dic_sommets_minimises={i:0 for i in range(n)}
dic_antecedants={i:0 for i in range(n)}
s,poids_sommets[s_a],dic_sommets_minimises[s_a]=s_a,0,1
while dic_sommets_minimises[s_b]==0:
# traitement du sommet: maj des poids des voisins
for j in range(n):
# seuls les voisins non optimises sont traités
if M[s][j] and dic_sommets_minimises[j]==0:
if poids_sommets[s]+M[s][j]<poids_sommets[j]:
poids_sommets[j]=poids_sommets[s]+M[s][j]
dic_antecedants[j]=s
# choix du prochain sommet: min des poids restants
poids_min=float('inf')
for j in range(n):
if dic_sommets_minimises[j]==0 and poids_sommets[j]<poids_min:
s_min,poids_min=j,poids_sommets[j]
dic_sommets_minimises[s_min]=1
s=s_min
# contruction du chemin suivi en remontant la liste des antécédants
chemin=[s_b]
while chemin[0]!=s_a:
chemin=[dic_antecedants[chemin[0]]]+chemin
# print(dic_antecedants)
return poids_sommets[s_b],chemin
On peut tester sur l'exemple donné en cours la correction des algorithmes précédents.
On commence par définir la matrice d'adjacence pondérée.
# Matrice du cours
MDij=np.zeros([7,7])
MDij[0,1]=3
MDij[0,2]=4
MDij[1,3]=5
MDij[1,5]=11
MDij[2,3]=3
MDij[2,4]=15
MDij[3,4]=10
MDij[3,5]=8
MDij[4,6]=14
MDij[5,6]=13
MDij=(MDij+MDij.transpose())
MDij=MDij.tolist()
# print(MDij)
On définit alors deux sommets : l'un de départ et l'autre d'arrivée et l'on exécute les deux programmes précédents.
depart=0
arrivee=4
cout=dijkstra(MDij,depart,arrivee)
print("Le chemin de {} à {} a une durée de {:.0f}".format(depart,arrivee,cout))
cout,chemin=dijkstra_chemin(MDij,depart,arrivee)
print("Le chemin de {} à {} a une durée de {:.0f} et suit le chemin suivant : {}".format(depart,arrivee,cout,chemin))
Le chemin de 0 à 4 a une durée de 17 Le chemin de 0 à 4 a une durée de 17 et suit le chemin suivant : [0, 2, 3, 4]