Parcours en largeur et plus court chemin
Le parcours en largeur commence à partir d'un sommet v, visite d'abord ce nœud et le marque comme visité, puis visite séquentiellement tous les voisins non visités {vi,..,vj} du nœud v et les marque comme visités, puis, pour chaque nœud dans {vi,...,vj}, répète la méthode de visite du nœud v jusqu'à ce que tous les nœuds aient été visités.
Nous pouvons le diviser en trois étapes :
- (1) Utilisez une file d'attente auxiliaire q. Enfilez d'abord le sommet v et marquez-le comme visité, puis bouclez pour vérifier si la file d'attente est vide.
- (2) Si la file d'attente n'est pas vide, retirez le premier élément de la file d'attente, enfilez tous les nœuds non visités associés à cet élément, et marquez ces nœuds comme visités.
- (3) Si la file d'attente est vide, cela signifie que tous les nœuds ont été parcourus dans l'ordre du parcours en largeur.
Comme le montre la figure ci-dessous, la partie bleue à droite indique l'ordre de parcours des nœuds à partir de 0, et la partie en dessous enregistre la distance depuis 0. On peut voir que le parcours en largeur permet de trouver le plus court chemin dans un graphe non pondéré.
Le code suivant montre comment effectuer un parcours à l'aide du parcours en largeur et interroger le plus court chemin. En nous basant sur le code de la section précédente, nous ajoutons une variable globale, le tableau ord, pour enregistrer l'ordre des nœuds dans le chemin. ord[i] représente l'ordre du nœud i dans le chemin. En même temps, le constructeur est ajusté en conséquence : lors du parcours des nœuds adjacents, chaque fois qu'un nœud non visité est visité, la distance est enregistrée sous la forme ord[i] = ord[v] + 1. La complexité temporelle du parcours en largeur utilisant une liste d'adjacence est O(V+E), et la complexité temporelle utilisant une matrice d'adjacence est O(V^2).
// Constructeur, algorithme de recherche de chemin, trouve les chemins du point s vers d'autres points du graphe
public ShortestPath(Graph graph, int s){
// Initialisation de l'algorithme
G = graph;
assert s >= 0 && s < G.V();
visited = new boolean[G.V()];
from = new int[G.V()];
ord = new int[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
from[i] = -1;
ord[i] = -1;
}
this.s = s;
// Algorithme de plus court chemin dans un graphe non orienté : en partant de s, effectuer un parcours en largeur de tout le graphe
LinkedList<Integer> q = new LinkedList<Integer>();
q.push( s );
visited[s] = true;
ord[s] = 0;
while( !q.isEmpty() ){
int v = q.pop();
for( int i : G.adj(v) )
if( !visited[i] ){
q.push(i);
visited[i] = true;
from[i] = v;
ord[i] = ord[v] + 1;
}
}
}
...
Vérifie la longueur du plus court chemin du point s au point w ; si w est inatteignable depuis s, renvoie -1.
public int length(int w){
assert w >= 0 && w < G.V();
return ord[w];
}
...
Exemple de code Java
Téléchargement du paquet de code source :Télécharger
Code du fichier src/example/graph/ShortestPath.java :
import example.graph.read.Graph;
import java.util.LinkedList;
import java.util.Stack;
import java.util.Vector;
/**
* Parcours en largeur et plus court chemin
*/
public class ShortestPath {
// Référence au graphe
private Graph G;
// Point de départ
private int s;
// Enregistrer si un nœud est visité pendant le DFS
private boolean[] visited;
// Enregistrer le chemin ; from[i] représente le nœud précédent de i sur le chemin de recherche
private int[] from;
// Enregistrer l'ordre des nœuds dans le chemin. ord[i] représente l'ordre du nœud i dans le chemin.
private int[] ord;
// Constructeur, algorithme de recherche de chemin, trouve les chemins du point s vers d'autres points du graphe
public ShortestPath(Graph graph, int s){
// Initialisation de l'algorithme
G = graph;
assert s >= 0 && s < G.V();
visited = new boolean[G.V()];
from = new int[G.V()];
ord = new int[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
from[i] = -1;
ord[i] = -1;
}
this.s = s;
// Algorithme de plus court chemin dans un graphe non orienté : en partant de s, effectuer un parcours en largeur de tout le graphe
LinkedList<Integer> q = new LinkedList<Integer>();
q.push( s );
visited[s] = true;
ord[s] = 0;
while( !q.isEmpty() ){
int v = q.pop();
for( int i : G.adj(v) )
if( !visited[i] ){
q.push(i);
visited[i] = true;
from[i] = v;
ord[i] = ord[v] + 1;
}
}
}
// Vérifier s'il existe un chemin du nœud s au nœud w
public boolean hasPath(int w){
assert w >= 0 && w < G.V();
return visited[w];
}
// Rechercher le chemin du nœud s au nœud w et le stocker dans vec
public Vector<Integer> path(int w){
assert hasPath(w) ;
Stack<Integer> s = new Stack<Integer>();
// En parcourant le tableau from, remonter le chemin de s à w et le stocker dans la pile
int p = w;
while( p != -1 ){
s.push(p);
p = from[p];
}
// Retirer les éléments de la pile un par un pour obtenir le chemin ordonné de s à w
Vector<Integer> res = new Vector<Integer>();
while( !s.empty() )
res.add( s.pop() );
return res;
}
// Afficher le chemin du nœud s au nœud w
public void showPath(int w){
assert hasPath(w) ;
Vector<Integer> vec = path(w);
for( int i = 0 ; i < vec.size() ; i ++ ){
System.out.print(vec.elementAt(i));
if( i == vec.size() - 1 )
System.out.println();
else
System.out.print(" -> ");
}
}
// Vérifier la longueur du plus court chemin du point s au point w
// Si le chemin de s à w est inaccessible, retourner -1
public int length(int w){
assert w >= 0 && w < G.V();
return ord[w];
}
}