M1 MABS Graphes TP Parcours en largeur - Plus court chemin
From silico.biotoul.fr
Contents |
Parcours en largeur
Algorithme :
BFS(G, s) for each vertex u V(G) do color[u] WHITE d[u] π[u] NIL color[s] GRAY d[s] 0 Q enqueue(Q, s) while Q do u dequeue(Q) for each vertex v Adj[u] do if color[v] = WHITE then color[v] GRAY d[v] d[u] + 1 π[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, s, w) 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)
Ajoutez la méthode à votre librairie et testez la sur le graphe File:M1MABS Graphe Bellman-Ford.tab à partir du sommet A.
Afin de gagner du temps, la méthode loadTAB vous est fournie :
def loadTAB(self, filename): """ Loads a graph in Cytoscape tab format Assumed input: id1 id2 weight color ... A B 6 blue ... """ with open(filename) as f: # GET COLUMNS NAMES tmp = f.readline().rstrip() attNames= tmp.split('\t') # REMOVES FIRST TWO COLUMNS WHICH CORRESPONDS TO THE LABELS OF THE CONNECTED VERTICES attNames.pop(0) attNames.pop(0) # PROCESS THE REMAINING LINES row = f.readline().rstrip() while row: vals = row.split('\t') v1 = vals.pop(0) v2 = vals.pop(0) att = {} for i in xrange(len(attNames)): att[ attNames[i] ] = vals[i] self.addEdge(v1, v2, att) row = f.readline().rstrip() # NEXT LINE
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émentez les méthodes FloydWarshall(W) et FloydWarshallPath(source, destination) dans votre librairie. Pour cela, vous êtes forcement incité(e) à ajouter une méthode adjacencyMatrix qui renvoie le graphe source forme de matrice d'adjacence.
Testez ces méthodes sur le graphe File:M1MABS Graphe Floyd-Warshall.tab et affichez les plus courts chemins de A à C et de A à B (avec leur longueur).