Discussion :

[geforce]

Bonjour a tous,

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

Mon code qui fait le parcourt d'un Graphe avec l'algorithme de Bellman-Ford: (input : model, output: noeudDistance)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 
/**
 * Source :
 * http://sourcecodesforfree.blogspot.ca/2013/05/21-bellman-ford-algorithm.html
 * http://youtu.be/ea38B7agTuM
 */
public class BellmanFord implements Algorithm {
    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>)
 
    //TODO Use une une liste de map (Matrice N*N)  //un Arbre du graphe (sous graphe)
 
    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
     * @return Tableau des plus coutre dictance du graphe
     */
    public Map<String, Double> bellmanFord(String source) {
        TreeModel treeModel = new TreeModel();
        Double newDistance = 0.0;
        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
 
            //TreeVertex rootVertex = new TreeVertex().setId(source).setDistance(newDistance);
        } else {
            throw new AlgorithmException("..... source node does not exist in the model");
        }
 
 
        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;
 
              //  TreeVertex sourceVertex = new TreeVertex().setId( model.getEdges().get(j).getSourceVertex().getId() ).setDistance(newDistance);
                newDistance = noeudDistance.get(model.getEdges().get(j).getSourceVertex().getId()) + model.getEdges().get(j).getWeight();       
              //  TreeVertex targetVertex = new TreeVertex().setId( model.getEdges().get(j).getTargetVertex().getId()  ).setDistance(newDistance);
 
 
                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);
 
                //    treeModel.addEdge( new TreeEdge().setSourceVertex( sourceVertex ).setTargetVertex( targetVertex) );
                }
 
            }
        }
 
        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!");
            }
        }
 
        //TODO : Du tableau je peu construire tout les noeuds de mon sous graphe (mon arbre)
        // puis comment je mes les bonne fleches 
        return this.noeudDistance;
    }
 
 
 
    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;
    }
 
 
    /** ******************************************** */
    /* ********************** ********************** */
 
}

Du résultat je dois extraire l'arbre des plus courts chemins ?


Voila un exemple :
Graphe initiale :


Le résultat de l'arbre que je veux extraire :


Merci d'avance pour vos suggestion.

[joel.drigo]

Salut,

C'est un problème d'algorithme, pas de Java, et ça se trouve avec un peu de recherche sur Internet.

[geforce]

C'est un problème d'algorithme, pas de Java, et ça se trouve avec un peu de recherche sur Internet.

Ce n'est pas le cas selon moi, l'Algorithme de Bellman-Ford de base ne donne pas en sortie un Arbre (avec les chemins),... fait que j'ai beaucoup cherché sur le .net avant de posé la question sur le forum.

Je n'ai pas si c'est utilisable, j'ai réfléchie modifié l'algorithme de base pour arrivé a sauvegardé les successeurs et les prédécesseurs dans une matrice carrée (du nombre de nœuds), mais je ne sais pas si c'est la bonne solution (j'ai réussi a le faire présentement), tout aide ou suggestion serais le bienvenu !?


Merci

[joel.drigo]

L'algorithme est une description de comment résoudre un problème, et ne dépend pas du langage. On pourrait l'encoder en Java, en C++, en JavaScript, ou en LISP...

Et en une recherche "graphes plus courts chemins" sur google, et 15 secondes de lecture, j'ai déjà une liste à étudier :

Plus courts chemins à origine unique :
Algorithme de Dijkstra
Algorithme de Ford-Bellman
Algorithme de Gabow

Plus courts chemins pour tout couple de sommets :

Algorithme de Floyd-Warshall
Algorithme de Johnson
Algorithme du flot maximum

Et pleins d'autres.

[kolodz]

Pour le coup, j'ai répondu sur le sujet dans la partie algorithmique... Dans dans ce sujet, il n'y avait pas présenté la partie profondeur associé à chaque lien.
Bien que la solution que j'ai donnée alors est exactement la même, malgré ce paramètre supplémentaire...

Je vais pas te faire l’offense de traduire l'algorithme que j'ai donnée en Java... A un moment, il faut bien que tu travail un peu...

Cordialement,
Patrick Kolodziejczyk.