M1 MABS Graphes TP Parcours en largeur - Plus court chemin
From silico.biotoul.fr
(Difference between revisions)
m (→Parcours en largeur) |
m |
||
| Line 2: | Line 2: | ||
Algorithme : | Algorithme : | ||
BFS(G, s) | BFS(G, s) | ||
| - | for each vertex u in V(G) | + | '''for each''' vertex u <math>\in</math> V(G) |
| - | do color[u] < | + | '''do''' color[u] <math>\leftarrow</math> white |
| - | d[u] < | + | d[u] <math>\leftarrow</math> inf |
| - | pred[u] < | + | pred[u] <math>\leftarrow</math> NIL |
| - | color[s] < | + | color[s] <math>\leftarrow</math> gray |
| - | d[s] < | + | d[s] <math>\leftarrow</math> 0 |
| - | Q < | + | Q <math>\leftarrow</math> <math>\empty</math> |
enqueue(Q, s) | enqueue(Q, s) | ||
| - | while Q <math>\ne</math> <math>\empty</math> | + | '''while''' Q <math>\ne</math> <math>\empty</math> |
| - | do u < | + | '''do''' u <math>\leftarrow</math> dequeue(Q) |
| - | for each v in Adj[u] | + | '''for each''' v <math>\in</math> Adj[u] |
| - | do if color[v] = white | + | '''do if''' color[v] = white |
| - | then color[v] < | + | '''then''' color[v] <math>\leftarrow</math> gray |
| - | d[v] < | + | d[v] <math>\leftarrow</math> d[u] + 1 |
| - | pred[v] < | + | pred[v] <math>\leftarrow</math> u |
enqueue(Q, v) | enqueue(Q, v) | ||
| - | color[u] < | + | color[u] <math>\leftarrow</math> black |
| - | Charger le graphe de la séance précédente ([[File:M1MABS Graphe dressing.sif]]), et | + | '''Charger''' le graphe de la séance précédente ([[File:M1MABS Graphe dressing.sif]]), et effectuer un parcours en largeur depuis sous-vetements. |
| + | = Plus court chemin - Bellman-Ford = | ||
| + | Rappel de l'algorithme: | ||
| + | |||
| + | |||
| + | <!-- | ||
= Plus court chemin - Dijkstra = | = Plus court chemin - Dijkstra = | ||
Pour l'algorithme suivant, | Pour l'algorithme suivant, | ||
| Line 57: | Line 62: | ||
'RFBD': 'RFBC', | 'RFBD': 'RFBC', | ||
'WBBK': 'WBBJ'}} | 'WBBK': 'WBBJ'}} | ||
| + | --> | ||
= Plus courts chemins - Floyd-Warshall = | = Plus courts chemins - Floyd-Warshall = | ||
Revision as of 15:22, 19 February 2015
Contents |
Parcours en largeur
Algorithme :
BFS(G, s) for each vertex uV(G) do color[u]
white d[u]
enqueue(Q, s) while Q
Charger le graphe de la séance précédente (File:M1MABS Graphe dressing.sif), et effectuer un parcours en largeur depuis sous-vetements.
Plus court chemin - Bellman-Ford
Rappel de l'algorithme:
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)
Implémenter les algorithmes ci-dessus en R et les tester sur la matrice suivante :
# adjacency matrix M=matrix( c(0,1,0,0,1,0,0,1,0,0,1,1,0,0,0,0), ncol=4, byrow=T) M # [,1] [,2] [,3] [,4] #[1,] 0 1 0 0 #[2,] 1 0 0 1 #[3,] 0 0 1 1 #[4,] 0 0 0 0 # test fw=FloydWarshall(M) fw #$distances # [,1] [,2] [,3] [,4] #[1,] 2 1 Inf 2 #[2,] 1 2 Inf 1 #[3,] Inf Inf 1 1 #[4,] Inf Inf Inf Inf # #$chemins # [,1] [,2] [,3] [,4] #[1,] 2 NA Inf 2 #[2,] NA 1 Inf NA #[3,] Inf Inf NA NA #[4,] Inf Inf Inf Inf FloydWarshallPath(fw, 1,4) #[1] 1 2 4
Extraire la grosse composante connexe de String au format sif puis transformer le fichier en matrice d'adjacence. Ensuite, sous R, charger la matrice et calculer le diamètre du graphe.
