Discussion :

[geforce]

Bonjour à tous,
J’ai réussi à comprendre et programmer l’algorithme de Bellman Ford qui lui permet de trouvé les plus court distance entre un nœud initiale et tous les autres nœuds (nœud quelconque) du graphe.

Mon algorithme de Bellman-Ford

Code Java :

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
 
public class BellmanFord implements Algorithm {
    private static final Double INF = Double.MAX_VALUE;
    private final Model model;
 
    private final Map<String, Double> noeudDistance; //remplace le comportement de int[] distance
 
 
    public BellmanFord(Model model) { 
        this.model = model; 
        this.noeudDistance = new HashMap<>();
    }
 
 
    /**
     * 
     * @param source Id du Noeud Start = le noeud source
     */
    public void bellmanFord(String source) {
        int nnodes = model.getVertices().size(); //nombre de Noeud 
 
        //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");
 
 
 
        for (int i = 0; i < nnodes; ++i)
            for (int j = 0; j < model.getEdges().size(); ++j) {
                if( noeudDistance.get( model.getEdges().get(j).getSourceVertex().getId() ).equals(INF) ) continue;
 
                Double 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 < model.getEdges().size(); ++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!");
 
    }
 
     //Display path //TODO améloration!!
      public void displayPath(String source) {
        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("The shortest distance between nodes " + source + " and " + i + " is " + this.noeudDistance.get("v"+i));
                System.out.println("Source : "+model.getEdges().get(i).getSourceVertex().getId() + " ,destination: "+model.getEdges().get(i).getTargetVertex().getId() +" ,weight :"+ model.getEdges().get(i).getWeight() );
                }
 
      }
 
}

Ma question :
Comment programativement il est possible de trouver et afficher un ou tous les plus courts chemin du graphe ? (je sais que je peu les trouvé avec visuellement mais je avoir une façon automatique)


Test avec junit :

Code Java :

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
 
public class BellmanFordTest {
 
    /**
     * Test of bellmanFord method, of class BellmanFord.
     */
    @Test
    public void testBellmanFord() {
        System.out.println("bellmanFord1");         
 
        Edge edgeA = new Edge(), edgeB = new Edge(), edgeC = new Edge(), edgeD = new Edge(), edgeE = new Edge(), edgeF = new Edge(), edgeG = new Edge(), edgeH = new Edge(); 
        Vertex vertexV0 = new Vertex(), vertexV1 = new Vertex(), vertexV2 = new Vertex(), vertexV3 = new Vertex(), vertexV4 = new Vertex();
 
        vertexV0.setId("v0").setName("v0"); vertexV1.setId("v1").setName("v1");
        vertexV2.setId("v2").setName("v2"); vertexV3.setId("v3").setName("v3"); vertexV4.setId("v4").setName("v4");
 
        edgeA.setId("Edge_A").setName("Edge_A").setSourceVertex(vertexV0).setTargetVertex(vertexV1).setWeight(2.0);
        edgeB.setId("Edge_B").setName("Edge_B").setSourceVertex(vertexV0).setTargetVertex(vertexV2).setWeight(6.0);
        edgeC.setId("Edge_C").setName("Edge_C").setSourceVertex(vertexV1).setTargetVertex(vertexV4).setWeight(2.0);
        edgeD.setId("Edge_D").setName("Edge_D").setSourceVertex(vertexV2).setTargetVertex(vertexV1).setWeight(3.0);
        edgeE.setId("Edge_E").setName("Edge_E").setSourceVertex(vertexV2).setTargetVertex(vertexV3).setWeight(2.0);
        edgeF.setId("Edge_F").setName("Edge_F").setSourceVertex(vertexV3).setTargetVertex(vertexV3).setWeight(0.0);        
        edgeG.setId("Edge_G").setName("Edge_G").setSourceVertex(vertexV4).setTargetVertex(vertexV3).setWeight(7.0);
        edgeH.setId("Edge_H").setName("Edge_H").setSourceVertex(vertexV4).setTargetVertex(vertexV2).setWeight(1.0);
 
 
 
       Model model = new Model()
                .addEdge(edgeA).addEdge(edgeB).addEdge(edgeC).addEdge(edgeD)
                .addEdge(edgeE).addEdge(edgeF).addEdge(edgeG).addEdge(edgeH);
 
        BellmanFord bellmanFord = new BellmanFord(model); //add Graphe
        bellmanFord.bellmanFord("v0"); //execution avec noeud init
 
        bellmanFord.displayPath("v0"); //Affichage
        //Display : v0, v1, v4, v2, v3
    }
 }

Merci

[yahiko]

Si tu as compris Bellman-Ford, il ne devrait pas il y avoir de problème pour récupérer les nœuds formant le(s) chemin(s) le plus court.
Il suffit juste de faire en sorte que ta fonction renvoie le chemin que tu as/auras construit au fur et à mesure du déroulement de l'algo.

[geforce]

Bien je crois qu'il m’a manqué des bouts, ou que je n'arrive pas à bien comprendre
Pourras tu me donnes plus de détail ou un exemple (avec ce qui j'ai fournis dans le 1er poste) pour affiché les chemins les plus courts ? (du nœud initial à tous les autres, j'ai peu affiché que les distances)

Merci d'avance de votre aide

[geforce]

Bonjour à tous,

après bien des recherches et des lectures, j'ai compris que l'algorithme de Bellman me permette d'avoir des plus courtes distances du graphe (d'un nœud initiale à un autre différent) mais aussi qui permet vraiment d'obtenir l'arborescence des plus courtes distances.

Donc comment je peux faire pour afficher tous les chemins possibles les plus courtes (à la place de juste les distance) ?

Merci