JAVA - Trouver l'arborescence des plus courts chemins

**geforce** · 24/02/2015, 05h48

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;
    }
 
 
    /** ******************************************** */
    /* ********************** ********************** */
 
}