2 pièce(s) jointe(s)
JAVA - Trouver l'arborescence des plus courts chemins
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:
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 ? :koi:
Voila un exemple :
Graphe initiale :
Pièce jointe 169890
Le résultat de l'arbre que je veux extraire :
Pièce jointe 169891
Merci d'avance pour vos suggestion.
