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
Partager