Algorithme de chemin le plus court de Dijkstra
Étant donné un graphe et un sommet source dans le graphe, recherchez les chemins les plus courts allant de la source à tous les sommets du graphe donné.
L’algorithme de Dijkstra est très similaire à celui de Prim pour l'arbre couvrant minimum. Comme Prim, nous générons un S (arbre du plus court chemin) avec une source donnée en tant que racine.
Nous maintenons deux ensembles, l'un contient les sommets inclus dans l'arbre du plus court chemin (S), l'autre ensemble comprend les sommets non encore inclus dans l'arbre de plus court (T). À chaque étape de l'algorithme, nous trouvons un sommet qui se trouve dans l'autre ensemble (ensemble de non encore inclus) et qui a une distance minimale par rapport à la source.
Ci-dessous sont les étapes détaillées utilisées dans l'algorithme de Dijkstra pour trouver le chemin le plus court d'un sommet source simple à tous les autres sommets dans le graphe donné.
- Créer un ensemble S(arbre du plus court chemin) qui garde la trace des sommets inclus dans l'arbre de chemin le plus court, c.-à-d., dont la distance minimale de la source est calculée et finalisée. Initialement, cet ensemble est vide.
- Attribuez une valeur de distance à tous les sommets du graphique d'entrée. Initialisez toutes les valeurs de distance comme INFINI. Attribuez la valeur de distance 0 pour le sommet source afin qu'il soit sélectionné en premier.
- Tandis que l'ensemble S ne comprend pas tous les sommets
- Choisissez un sommet u qui n'est pas dans l'ensemble S et qui a une valeur de distance minimale.
- Incluez u à S.
- Pour chaque successeur v de u, avec v dans T, faire
- si la somme de la valeur de la distance de u (de la source) et le poids de l'arête u-v, est inférieure à la valeur de la distance de v
- mettre à jour la valeur de distance de v.
- si la somme de la valeur de la distance de u (de la source) et le poids de l'arête u-v, est inférieure à la valeur de la distance de v
import math
class Graphe():
def __init__(self, noeuds):
self.matriceAdj = noeuds.copy()
def Afficher(self, src, dist):
print("les chemins les plus courts allant de ", src, " est : ")
for noeud in range(len(self.matriceAdj)):
print((noeud+1), "\t", dist[noeud])
def minDistance(self, dist, S, T):
# Initialiser la distance minimale pour le nœud
min = math.inf
min_index = -1
for v in T:
if dist[v-1] < min:
min = dist[v-1]
min_index = v-1
# supprimer de T et ajouter dans S
T.remove(min_index+1)
S.append(min_index+1)
return min_index
def dijkstra(self, src):
dist = [math.inf] * len(self.matriceAdj)
precedence = [-1] * len(self.matriceAdj)
dist[src-1] = 0
precedence[src-1] = src-1
S = []
T = [(i+1) for i in range(len(self.matriceAdj))]
while len(S) < len(self.matriceAdj):
# Choisir un sommet u qui n'est pas dans l'ensemble S et
# qui a une valeur de distance minimale
u = self.minDistance(dist, S, T)
# relaxation des sommets
for v in range(len(self.matriceAdj)):
if (self.matriceAdj[u][v] > 0) and (dist[v] > (dist[u] + self.matriceAdj[u][v])):
dist[v] = dist[u] + self.matriceAdj[u][v]
precedence[v] = u
self.Afficher(src, dist)
# Test
# les sommets sont numérotés à partir de 1
matriceAdj = [[0, 2, 4, 0, 0, 0],
[0, 0, 1, 0, 7, 0],
[0, 0, 0, 3, 0, 0],
[0, 0, 0, 0, 2, 5],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0],
]
g = Graphe(matriceAdj)
g.dijkstra(1)
1 -> 0
2 -> 2
3 -> 3
4 -> 6
5 -> 8
6 -> 9
Exemple :
L'ensemble S est initialement vide et les distances attribuées aux sommets sont {0, INF, INF, INF, INF, INF, INF}, où INF signifie infini.
Choisissez maintenant le sommet avec la valeur de distance minimale. Le sommet 1 est sélectionné, incluez-le dans S. Donc, S devient {1}.
Après avoir inclus 1 dans S, mettez à jour les valeurs de distance de ses sommets adjacents. Les sommets adjacents de 1 sont 2 et 3. Les valeurs de distance de 2 et 3 est 2 et 4 respectivement.
Après que le sous-graphe affiche les sommets et leurs valeurs de distance, seuls les sommets avec des valeurs de distance finies sont affichés. Les sommets inclus dans S sont affichés en couleur verte.
Sélectionnez le sommet avec la valeur de distance minimale et non déjà inclus dans S. Le sommet 2 est sélectionné et ajouté à S. Donc, S devient maintenant {1, 2}. Mettez à jour les valeurs de distance des sommets adjacents de 2. La valeur de distance de sommets {3, 5} devient {3, 9}.
Sélectionnez le sommet avec la valeur de distance minimale et non déjà inclus dans S. Le sommet 3 est sélectionné et ajouté à S. Donc, S devient maintenant {1, 2, 3}. Mettez à jour les valeurs de distance des sommets adjacents de 3. La valeur de distance du sommet 4 devient 6.
Nous répétons les étapes ci-dessus tant que S n'inclu pas tous les sommets d'un graphe donné. Enfin, nous obtenons l’arbre de chemin le plus court suivant.
