Arborescence des plus courts chemins.

Le parcours d'un graphe , c'est à dire la recherche de chemins entre deux sommets revient au calcul de certaines arborescences dont l'ensemble des sommets et des arcs sont inclus dans et respectivement. Nous commençons par décrire celle des plus courts chemins.

  
Figure: Une arborescence des plus courts chemins de racine

L'existence de l'arborescence des plus courts chemins est une conséquence de la remarque suivante:
Remarque Si est un plus court chemin entre et alors, pour tout i tel que , est un plus court chemin entre et .

Preuve On considère la suite d'ensembles de sommets construite de la façon suivante:

• .

• est l'ensemble des successeurs de , duquel il faut éliminer si le graphe possède un arc ayant pour origine et pour extrémité.

• est l'ensemble des successeurs d'éléments de qui n'appartiennent pas à .

D'autre part pour chaque , , on construit l'ensemble d'arcs contenant pour chaque un arc ayant comme extrémité et dont l'origine est dans . On pose ensuite: . Le graphe est alors une arborescence de par sa construction même, le fait qu'il s'agisse de l'arborescence des plus courts chemins résulte de la remarque ci-dessus.
La figure donne un exemple de graphe et une arborescence des plus courts chemins de racine , celle-ci est représentée en traits gras, les ensembles et sont les suivants:

La preuve de ce théorème, comme c'est souvent le cas en mathématiques discrètes se transforme très simplement en un algorithme de construction de l'arborescence .   Cet algorithme est souvent appelé algorithme de parcours en largeur ou breadth-first search, en anglais. Nous le décrivons ci dessous, il utilise une file avec les primitives associées: ajout, suppression, valeur du premier, test pour savoir si la file est vide. La file gère les ensembles . On ajoute les éléments des successivement dans la file qui contiendra donc les les uns à la suite des autres. La vérification de ce qu'un sommet n'appartient pas à se fait à l'aide du prédicat (pere[y] = omega).    

procedure ArbPlusCourt (succ: GrapheSuc; n: integer; x: Sommet; 
                        var pere: Arbo);
    var
        f: Fil;
        u, v: Sommet;
        i: integer;
    begin
    InitialiserFile(f);
    for u := 1 to n do
        pere[u] := Omega;
    Fajouter(x, f);
    pere[x] := x;
    while not (Fvide(f)) do
        begin
        u := Fvaleur(f);
        Fsupprimer(f);
        i := 1;
        v := succ[u, i];
        while (v <> Omega) do
            begin
            if (pere[v] = Omega) then
                begin
                pere[v] := u;
                Fajouter(v, f);
                end;
            i := i + 1;
            v := succ[u, i];
            end;
        end;
    end;