Revision as of 15:30, 19 February 2015

Parcours en largeur

Algorithme :

BFS(G, s)
  for each vertex u  V(G)
    do color[u]  white
       d[u]  inf
       pred[u]  NIL
  color[s]  gray
  d[s]  0
  Q  
  enqueue(Q, s)
  while Q  
    do u  dequeue(Q)
      for each v  Adj[u]
        do if color[v] = white
          then color[v]  gray
               d[v]  d[u] + 1
               pred[v]  u
               enqueue(Q, v)
      color[u]  black

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:

 INITIALIZE-SINGLE-SOURCE(G, s)
   for each vertex v  V(G)
     do d[v]  
         $π$ [v]  NIL
   d[s]  0
 RELAX(u, v, w)
   if d[v] > d[u] + w(u, v)
     then d[v] = d[u] + w(u,v)
           $π$ [v]  u
 BELLMAN-FORD(G, w, s)
   INITIALIZE-SINGLE-SOURCE(G, s)
   for i  1 to |V(G)| - 1
     do for each edge (u,v)  E(G)
       do RELAX(u, v, w)

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.

@@ Line 24: / Line 24: @@
 = Plus court chemin - Bellman-Ford =
 Rappel de l'algorithme:
+  INITIALIZE-SINGLE-SOURCE(G, s)
+    '''for each''' vertex v <math>\in</math> V(G)
+      '''do''' d[v] <math>\leftarrow</math> <math>\infty</math>
+         <math>\pi</math>[v] <math>\leftarrow</math> NIL
+    d[s] <math>\leftarrow</math> 0
+  RELAX(u, v, w)
+    '''if''' d[v] > d[u] + w(u, v)
+      '''then''' d[v] = d[u] + w(u,v)
+           <math>\pi</math>[v] <math>\leftarrow</math> u
+  BELLMAN-FORD(G, w, s)
+    INITIALIZE-SINGLE-SOURCE(G, s)
+    '''for''' i <math>\leftarrow</math> 1 '''to''' |V(G)| - 1
+      '''do for each''' edge (u,v) <math>\in</math> E(G)
+        '''do''' RELAX(u, v, w)
 <!--

M1 MABS Graphes TP Parcours en largeur - Plus court chemin

From silico.biotoul.fr

Revision as of 15:30, 19 February 2015

Contents

Parcours en largeur

Plus court chemin - Bellman-Ford

Plus courts chemins - Floyd-Warshall

Données