M1 MABS Graphes TP Parcours en largeur - Plus court chemin
From silico.biotoul.fr
(Difference between revisions)
m (→Parcours en profondeur) |
m (→Plus court chemin - Dijkstra) |
||
Line 32: | Line 32: | ||
P[successeur] = x | P[successeur] = x | ||
+ | Extraire la composante connexe contenant WBBJ, puis faire tourner l'algorithme ci-dessus à partir de WBBJ. | ||
+ | Résultat attendu : | ||
+ | {'distances': | ||
+ | {'WBBI': 29, | ||
+ | 'WBBH': 34, | ||
+ | 'RFBX': 71, | ||
+ | 'WBBJ': 0, | ||
+ | 'RFBC': 103, | ||
+ | 'RFBD': 104, | ||
+ | 'WBBK': 6}, | ||
+ | 'predecessors': { | ||
+ | 'WBBI': 'WBBK', | ||
+ | 'WBBH': 'WBBK', | ||
+ | 'RFBX': 'WBBJ', | ||
+ | 'RFBC': 'RFBX', | ||
+ | 'RFBD': 'RFBC', | ||
+ | 'WBBK': 'WBBJ'}} | ||
= Plus courts chemins - Floyd-Warshall = | = Plus courts chemins - Floyd-Warshall = |
Revision as of 11:00, 20 February 2013
Parcours en profondeur
Algorithme :
BFS(graphe g, sommet s) f = créerFile marquer(s) enfiler(f,s) tant que f n'est pas vide x = défiler(f) afficher(x) pour chaque successeur de x faire si successeur n'est pas marqué alors marquer(successeur) enfiler(f, successeur)
Charger le graphe de la séance précédente, et faire un parcours en largeur depuis WBBJ.
Plus court chemin - Dijkstra
Pour l'algorithme suivant,
- D[x] donne la plus courte distance entre s et x. Au départ, D[s]=0 et D[x]=infini pour tout x différent s.
- P[x] est le prédécesseur de x dans le chemin de plus courte distance allant de s à x. Au départ, P[x]=rien pour tout x.
- C est l'ensemble de sommets qu'il reste à parcourir. Au départ, C=V (V étant l'ensemble des sommets du graphe).
- W[x,y] est la valuation de l'arc (x,y)
Algorithme :
Dijkstra(graphe g, sommet s) initialiser D, P et C tant que C n'est pas vide faire x = extraire le sommet le plus proche de C pour chaque successeur de x faire si D[x] + W[x,successeur] < D[successeur] alors D[successeur] = D[x] + D[successeur] P[successeur] = x
Extraire la composante connexe contenant WBBJ, puis faire tourner l'algorithme ci-dessus à partir de WBBJ. Résultat attendu :
{'distances': {'WBBI': 29, 'WBBH': 34, 'RFBX': 71, 'WBBJ': 0, 'RFBC': 103, 'RFBD': 104, 'WBBK': 6}, 'predecessors': { 'WBBI': 'WBBK', 'WBBH': 'WBBK', 'RFBX': 'WBBJ', 'RFBC': 'RFBX', 'RFBD': 'RFBC', 'WBBK': 'WBBJ'}}
Plus courts chemins - Floyd-Warshall
Pour l'agorithme suivant,
- D[x,y] est la distance du plus court chemin entre les sommets x et y
- N[x,y] est le successeur de x dans le plus court chemin allant de x à y
- W[x,y] est la valuation de l'arc (x,y)
Algorithme :
initialiser D = W, et N pour k de 1 à n pour i de 1 à n pour j de 1 à n si D[i,k] + D[k,j] < D[i,j] alors D[i,j] = D[i,k] + D[k,j] N[i,j] = k
Récupération du plus court chemin à partir de la matrice N :
plusCourtChemin(D,N, i,j) si D[i,j] est infinie alors il n'y a pas de chemin entre i et j chemin = initialiserChemin(i) k = N[i,j] tant que k est défini faire ajouter(chemin, k) k = N[k,j] ajouter(chemin, j)