Trouver l'arborescence des plus courts chemins (algorithme de Bellman-Ford)

Version imprimable

22/02/2015, 07h07
geforce

Trouver l'arborescence des plus courts chemins (algorithme de Bellman-Ford)

Bonjour à tous,
Sur l'algorithme de Bellman-Ford, de base en output en a jute les plus courtes distances.

Moi je cherche à enregistrer l'arbre des plus courts chemins, issue du sommet V0, dans un graphe.

Comment ces possibles ? (si c'est possible)

Merci.

Donc voilà j'ai fait ma version de l'algorithme ci-dessous :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
public class BellmanFord implements Algorithm {
//    public static TreeModel treeDisplay = null;  //un Arbre du graphe (sous graphe)
 
    private static final Double INF = Double.MAX_VALUE;
    private final Model model;                     //Input of the classe (un graphe)
 
    private final Map<String, Double> noeudDistance; //Output of the classe (liste de <Noeud, plus courte distance>)
 
    public BellmanFord(Model model) {
        this.model = model;
        this.noeudDistance = new HashMap<>();
    }
 
    /**
     * Les noeud Source et destination sont designer par des String
     *
     * @param source Id du Noeud Start = le noeud source
     */
    public void bellmanFord(String source) {
        int nNodes = model.getVertices().size(); //nombre de Noeud 
        int nEdges = model.getEdges().size();
 
        //initialisation de la Map (tableau aociative) avec + l'infinit 
        for (org.graphwalker.core.model.Vertex vertex : model.getVertices()) {
            noeudDistance.put(vertex.getId(), INF);
        }
 
        //initalisation de la distance a 0 pour le noeud Source; 
        if (noeudDistance.containsKey(source)) {
            noeudDistance.remove(source);
            noeudDistance.put(source, 0.0); //les noeud source = zero
        } else {
            throw new AlgorithmException("..... source node does not exist in the model");
        }
 
        Double newDistance = 0.0;
        for(int i = 0; i < nNodes; ++i) {
            for (int j = 0; j < nEdges; ++j) {
                if (noeudDistance.get(model.getEdges().get(j).getSourceVertex().getId()).equals(INF)) {
                    continue;
                }
 
                newDistance = noeudDistance.get(model.getEdges().get(j).getSourceVertex().getId()) + model.getEdges().get(j).getWeight();       
 
                if (newDistance < noeudDistance.get(model.getEdges().get(j).getTargetVertex().getId())) {
                    String tmp = model.getEdges().get(j).getTargetVertex().getId();
                    noeudDistance.remove(tmp); noeudDistance.put(tmp, newDistance);
                }
 
            }
        }
 
        for (int i = 0; i < nEdges; ++i) {
            if (!INF.equals(noeudDistance.get(model.getEdges().get(i).getSourceVertex().getId()))
                    && noeudDistance.get(model.getEdges().get(i).getTargetVertex().getId()) > noeudDistance.get(model.getEdges().get(i).getSourceVertex().getId()) + model.getEdges().get(i).getWeight()) {
                throw new AlgorithmException("Negative edge weight cycles detected!");
            }
        }
 
    }
 
 
 
    public void displayPath(String source) { //returne 'TreeModel'
        for (int i = 0; i < this.noeudDistance.size(); ++i) {
            if (INF.equals(this.noeudDistance.get(i))) System.out.println("There's no path between " + source + " and " + i);
            else 
 
            System.out.println(
            "= ================================================== = "+System.getProperty("line.separator")+
            "The shortest distance between nodes " + source + " and " + i+"v"+" is " + this.noeudDistance.get("v"+i)+System.getProperty("line.separator")+
            " Source : "+model.getEdges().get(i).getSourceVertex().getId() + " ,destination: "+model.getEdges().get(i).getTargetVertex().getId() +" ,weight :"+ model.getEdges().get(i).getWeight() +System.getProperty("line.separator")+
            "= ================================================== = ");
 
        }
 
        //Quel chemain tu veux 
        //Ex: v0-->v4 //Path: v0-v1-v2-v4 dist-min:7
//        return treeDisplay;
    }
 
 
    /** ******************************************** */
    /* ********************** ********************** */
 
}

mais il reste comme extraire l'arbre des plus courts chemins ? (j'ai du mal à trouver comment faire )

NB: il faut extraire le sous graphe du graphe initial (sous graphe est : un arbre des plus courte distance) .... hmmm je c'est pas si je dois utilisé les successeur et / prédécesseur

Citation:

Je ne sais pas si je peu exploré cette picte:
1- Du tableau (noeudDistance) je peux construire tous les nœuds de mon sous graphe (mon arbre).
2- de 1 Comment je mets les bonnes flèches ?

Merci D'avance

24/02/2015, 10h40
kolodz

C'est juste une question de parcours, il y a absolument rien de compliqué dans ton problème.

Notons A le plus court chemin déjà trouvé.
On initialise cette valeur à une valeur maximal de l'unité de mesure utilisé (exemple Java Integer.MAX_VALUE)
On commence le parcours de l'arbre branche à branche.

Dès qu'on trouve un nœud final, on note la profondeur actuel. (Et le chemin parcours)
Dès qu'on décences à une profondeur supérieur à A. On remonte d'un cran dans arborescence et on passe au suivant.

Cordialement,
Patrick Kolodziejczyk.
25/02/2015, 01h35
geforce

Hi, Patrick

J'ai déjà fait tout C'est étape (voir mon code plus haut qui fonctionne très bien).

Mais c'est l'étape suivant, j'ai trop cherché comment faire :

Citation:

Envoyé par kolodz

Dès qu'on trouve un nœud final, on note la profondeur actuel. (Et le chemin parcours)

Ce n'ai pas aussi simple que juste au parcoure saisir ou noté les la profondeur actuel. (Et le chemin parcours) !! il faut le chemin le plus courts, par exemple si en est dans un nœud profondeur 1 = a 1d et que profondeur 2 = 18d alors qu'un autre chemin après le 6ém profondeur deviens plus cours que le 1er donc notre chemin le plus cours est le 2em et pas le 1er picte mais en peu le savoir que âpres 6 profondeur plus bas.

D'ou ma question de comment Trouver l'arborescence des plus courts chemins ? (algorithme de Bellman-Ford que j'ai fait voir mon code plus haut... je peu donnes plus de détail si besoin)

NB: voilà version plus pratique de la question (idéalement a d’adapté a mon code java.... c'est le besoin que j'ai)
http://www.developpez.net/forums/d15...ourts-chemins/
25/02/2015, 10h08
kolodz

Cela est parce que tu ne parcours pas ton arbre proprement. Quand tu parcours un arbre à chaque itération tu note les nœuds emprunté. D'ailleurs, le calcule de la profondeur peu se faire progressivement... Tu ne te retrouve donc jamais au nœud final sans savoir par quel parent tu es passé !

Dans le cas, où tu as :

Citation:

Envoyé par Cas

S0>S1>S2>S3>SF (Distance total 20)
S0>S2>S5>SF (Distance total 30)
S0>S3>SF (Distance total 10)

Citation:

Envoyé par Déroulement de l'algo

quand tu va parcourir ton arbre tu va débuté à S0 profondeur max = l'infini :
Tu prends le premier enfant S1.
Ce n'est pas ton nœud final, et la profondeur courent est inférieur au maximum.
Tu prend le premier enfant S2.
Ce n'est pas ton nœud final, et la profondeur courent est inférieur au maximum.
Tu prend le premier enfant S3.
Ce n'est pas ton nœud final, et la profondeur courent est inférieur au maximum.
Tu prend le premier enfant SF.
C'est ton nœud final, tu remplace la profondeur maximal par la profondeur actuel. (20<infini)
Tu dépile SF.
Tu prend le nœud suivant enfant. Mais, il n'y en a pas donc tu dépile S3.
Tu prend le nœud suivant enfant. Mais, il n'y en a pas donc tu dépile S2.
Tu prend le nœud suivant enfant. Mais, il n'y en a pas donc tu dépile S1.
Tu prend le nœud suivant enfant, S2.
Ce n'est pas ton nœud final, et la profondeur courent est inférieur au maximum.
Tu prend le nœud suivant enfant, S5.
Ce n'est pas ton nœud final, et la profondeur courent est supérieur au maximum.(25>20)
Tu dépile S5.
Tu prend le nœud suivant enfant. Mais, il n'y en a pas donc tu dépile S2.
Tu prend le nœud suivant enfant, S3.
Ce n'est pas ton nœud final, et la profondeur courent est inférieur au maximum.
Tu prend le premier enfant SF.
C'est ton nœud final,(et la profondeur est inférieur à la profondeur maximum) tu remplace la profondeur maximal par la profondeur actuel. (10<20)
Tu dépile SF.
Tu prend le nœud suivant enfant. Mais, il n'y en a pas donc tu dépile S3.
Tu prend le nœud suivant enfant. Mais, il n'y en a pas donc tu dépile S0.
Fin de l'algo.

Tu trouve ton chemin le plus court à savoir S0>S3>SF. De manière systématique !

Cordialement,
Patrick Kolodziejczyk.
26/02/2015, 03h57
geforce

Citation:

Envoyé par kolodz

Cela est parce que tu ne parcours pas ton arbre proprement. Quand tu parcours un arbre à chaque itération tu note les nœuds emprunté. D'ailleurs, le calcule de la profondeur peu se faire progressivement... Tu ne te retrouve donc jamais au nœud final sans savoir par quel parent tu es passé !

Dans le cas, où tu as :

Tu trouve ton chemin le plus court à savoir S0>S3>SF. De manière systématique !

Cordialement,
Patrick Kolodziejczyk.

Quand tu dit dépilé : c'est le retour de la récursivité c'est un peu avec ça que tu trace ton chemin (mais c'est pas mon cas voir cette exemple ... selon moi tu a pas le bon exemple ou tu ma pas compris)

Donc :
initialement j'ai ça : (avec une structure d'objet java j'arrive a le reproduire)
Pièce jointe 169890

puis je pas sur lui l’algorithme suivant (c'est comme obligatoire - qui que ce lui de Bellman-Ford)
Source 1 : http://sourcecodesforfree.blogspot.c...algorithm.html
Source 2 : http://youtu.be/ea38B7agTuM

Donc en sortie en a une chose du style : Tab: (A, 0), (B, 2), (E, 5), (D, 7), (C, 1). ce n'est que les les distances les plus court du noeud A vers tout les autres.

Mais moi a la place je veux ça : (Comment faire, du tableau TAB) ce qui suit :
Pièce jointe 169891
26/02/2015, 10h13
kolodz

Je vais te faire l'algorithme que je t'ai présenté sur l'ensemble des nœuds de ton graph initial :
A: Point initial
On prend A, on est arrivé Distance 0.
Chemin optimal pour A: A(0)

B :
On prend A, ce n'est pas notre nœud final.
On prend B, c'est le nœud qu'on cherche. On met à jour la distance maximal => 2.
On dépile B.
On prend E
On prend C. La distance courante est supérieur à 2 (6>2)
On dépile C.
On a fini.
Chemin optimal pour B : A->2->B

C:
On prend A, ce n'est pas notre nœud final.
On prend B, ce n'est pas notre nœud final.
On prend E, ce n'est pas notre nœud final.
On prend D, ce n'est pas notre nœud final.
D n'est pas d'enfant, on dépile D.
E n'as plus d'enfant, on dépile E.
On prend C, c'est le nœud qu'on cherche. On met à jour la distance maximal => 5.
On dépile C.
B n'as plus d'enfant, on dépile B.
On prend E, ce n'est pas notre nœud final.
On prend D, ce n'est pas notre nœud final.
D n'est pas d'enfant, on dépile D.
E n'as plus d'enfant, on dépile E.
On prend C, c'est le nœud qu'on cherche. Mais on est supérieur à la valeur maximal (6>5)
On dépile C.
On a fini.
Chemin optimal pour C : A->2->B->3->C

D:
On prend A, ce n'est pas notre nœud final.
On prend B, ce n'est pas notre nœud final.
On prend E, ce n'est pas notre nœud final.
On prend D, c'est le nœud qu'on cherche. On met à jour la distance maximal => 11.
On dépile D.
On dépile E.
On prend C
On prend D, c'est le nœud qu'on cherche. On met à jour la distance maximal => 7.
On dépile D.
On dépile C.
On dépile B.
On prend E.
On prend D, c'est le nœud qu'on cherche. Mais on est supérieur à la valeur maximal (8>7)
On dépile D
On dépile E.
On prend C.
On prend D, c'est le nœud qu'on cherche. Mais on est supérieur à la valeur maximal (8>7)
On dépile D
On dépile C
On a finit.
Chemin optimal pour D : A->2->B->3->-C>2->D

E
On prend A, ce n'est pas notre nœud final.
On prend B, ce n'est pas notre nœud final.
On prend E, c'est le nœud qu'on cherche. On met à jour la distance maximal => 4.
On dépile E.
On prend C, ce n'est pas notre nœud final. Et la distance est supérieur à la distance maximal.
On dépile C.
On dépile B.
On prend E, c'est le nœud qu'on cherche. On met à jour la distance maximal => 1.
On dépile E
On prend C, ce n'est pas notre nœud final. Et la distance est supérieur à la distance maximal.
On dépile C.
On a fini.
Chemin optimal pour E : A->1->E

On obtient donc :

Citation:

Envoyé par Arbre

A->2->B->3->-C>2->D
A->1->E

Ce qui n'est pas l'arbre que tu as dans ton résultat, mais c'est celui qui est correcte.

De même si un nœud est présent dans le chemin optimal d'un autre nœud, sont chemin optimal est aussi calculé.

Cordialement,
Patrick Kolodziejczyk.
09/03/2015, 04h55
geforce

J'ai une autre priorité, mais je reviens à mon sujet ton bien que mal.

Merci pour la correction du chemin je ne me suis pas rendu compte, puis là je vais voir si je peux adapter ton déroulement à mon algorithme de Ford-Bellman

bonjour

Ton Algo "pete sec" car est incomplet ...Il manque une autre table pour memoriser les "predecessors" et la mettre à jour avec le tableau des distances...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
 Proc SorthestPath(G,Source)
   private int  pred[]   //numero du noeud predecessor (ou en java un map vers string )
   private  double dist[]
   ForEach v in V do
       dist[v]=infini
       pred[v]=-1
      dist[Source]=0
      For i  to N-1 do  (n :nbre de vertex)
          For Each edge(u,v)  in E do
                newLen=dist[u]+weight of edge(u,v)
                if (newLen < dist[v] ) then
                    dist[v]=newLen
                    pred[v]=u  'ici que ca se passe
                endif
          EndForEach 'boucle edge
      EndFor 'boucle i
   EndForEach 'boucle vertex
End Proc

Apres le tableau dist indique la distance depuis un noeud terminal -V-vers Source et TRIVIALEMENT on peut remonter depuis -V- vers Source avec une boucle while

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
Proc PrintAllPath(Souce:vertex)
      ForEach v in V do
         print dist[v]
         PrintPath(v,Source)
EndProc 
Proc PrintPath(v:vertex,Source:vertex)
 
   while  v <> Source  'tant que pas Source on remonte
     u = pred[v]
     print u 'imprime u
   EndWhile
EndProc

et voila ...!!!

re
Oups ! une ligne fatidique manque dans la boucle While de la Proc PrintPath...La voici (vu l'heure du post ou certains ronflent à poings fermes):
Code:

1 2 3 4 5 6 7 8 9 10 11 Proc PrintPath(v:vertex,Source:vertex) while v <> Source 'tant que pas Source on remonte u = pred[v] print u 'imprime u v=u 'sans cette maj vitale la boucle serait infinie et inutile... EndWhile EndProc
Ce qui fait sourire chez les debutants ,c'est toujours de vouloir trouver quelque chose dont il n'ont pas au prealable fait provision....!!!

10/03/2015, 04h49
geforce

Bonjour MABROUKI
il me somble qu'il y des manque, c'est pas sufisant de mettre juste cela (1er Algo)

Citation:

pred[v]=u 'ici que ca se passe

il faut un cas ou mettre a jours le path si en ce rende comte que ce n'est pas notre bon chemin (en terme de distance) pour ton tableau pred[v] des prédécesseur par nœud (vertex) que tu parcours avec Belman-Ford
10/03/2015, 22h02
MABROUKI

Re
Il me semble que tu as de gros probleme avec cet Algo pourtant simple...le tableau Pred a ete mis invente par Mr Bellman lui-meme dans sa version originale pour justement "recorder" les predecesseurs de chaque noeud -v- pour lequel on compute la distance minimale vers le sommet...
Si tu veux une image ,ce Pred ,c'est peu les "cailloux" du Petit Poucet (dont il a fait provision au depart) et qu'il laisse à chaque carrefour du chemin le moins long(if newLen) pour pouvoir plus tard remonter vers la Source...
Bref pour moi c'est clair...
11/03/2015, 05h39
geforce

Oui j'ai résolue cette problématique :zoubi: merci je suis sur un autre je partage mon code des que possible pour avoir vos remarques