from dataclasses import dataclass
#classe qui représente un arc pondéré départ -----poids--------> arrive
@dataclass
class ArcPondere:
depart: int
arrive: int
poids: int
class GraphePondere:
def __init__(self, nbSommets):
self.listeAdjacences = [ [] for i in range(nbSommets) ]
def ajouterArc(self, depart, arrive, poids):
self.listeAdjacences[depart].append(ArcPondere(depart, arrive, poids))
def getArcsPartantDe(self, depart):
return self.listeAdjacences[depart]
def getNbSommets(self):
return len(self.listeAdjacences)
G = GraphePondere(5)
G.ajouterArc(0, 3, 7)
G.ajouterArc(0, 1, 3)
G.ajouterArc(1, 2, 5)
G.getArcsPartantDe(0)
class GrapheMatricePondere:
def __init__(self, nbSommets):
self.matrice = [ [0 for i in range(nbSommets)] for j in range(nbSommets) ]
def ajouterArc(self, depart, arrive, poids):
self.matrice[depart][arrive] = poids
def getArcsPartantDe(self, depart):
for arrive in range(len(self.matrice[depart])):
if self.matrice[depart][arrive] > 0:
yield ArcPondere(depart, arrive, self.matrice[depart][arrive])
def getNbSommets(self):
return len(self.matrice)
G2 = GrapheMatricePondere(5)
G2.ajouterArc(0, 3, 7)
G2.ajouterArc(0, 1, 3)
G2.ajouterArc(1, 2, 5)
G2.matrice
G2.getArcsPartantDe(0)
import math
#file de priorité implémenté avec un tableau non trié
class FilePriorite:
#initialise la file de priorité avec les éléments 0 à n-1 où le tableau priorites donne les priorités, i.e. la priorité
#de l'élément i est priorites[i]
def __init__(self, priorites):
self.priorites = priorites
self.elements = [i for i in range(len(priorites))]
self.nbElements = len(priorites)
#retourne, et supprime de la file, l'élément prioritaire (i.e. avec une valeur de priorité minimale)
def defilerMin(self):
self.nbElements = self.nbElements - 1
iMinJusquici = -1
minJusquici = math.inf
for i in range(len(self.priorites)):
if(self.elements[i] != None):
if(self.priorites[i] < minJusquici):
minJusquici = self.priorites[i]
iMinJusquici = i
self.elements[iMinJusquici] = None
return iMinJusquici
def estVide(self):
return self.nbElements == 0
#cette fonction ne fait rien (mais il y en a besoin pour les tas, une implémentation plus efficace des files
#de priorité).
#Elle est présente pour que l'on puisse utiliser cette implémentation dans Dijkstra qui appelle cette fonction
def diminuerPriorite(self, element):
return
f = FilePriorite([10, 8, 23])
[f.defilerMin(), f.defilerMin(), f.defilerMin()]
import math
def dijkstra(G, s):
d = [math.inf for i in range(G.getNbSommets())]
d[s] = 0
f = FilePriorite(d)
while not f.estVide():
u = f.defilerMin()
for arc in G.getArcsPartantDe(u):
if d[arc.arrive] > d[u] + arc.poids:
d[arc.arrive] = d[u] + arc.poids
f.diminuerPriorite(arc.arrive)
return d
dijkstra(G2, 0)