JGraphT vermeiden Schleifen (Bellman Ford)

Question

Ich benutze JGraphT für die Implementierung eines Bellman Ford kürzesten Pfad-Algorithmus in Java. Da es einige Kanten gibt, die vorzuziehen sind, wird deren Kantengewicht auf -1 gesetzt.

Zum Beispiel:

< A -> B: 10

< A -> C: 10

< C -> B: -1

< B -> D : 10

In diesem Fall sollte der Pfad wie folgt aussehen: A -> C -> B -> D. Der Unterpfad A- > C-> B ist A-> B vorzuziehen.

Jetzt ist das Problem: Der Algorithmus findet Schleifen zwischen C und B, so dass die C-> B und B-> C Pfade mehrmals hinzugefügt werden (um die gesamten Pfadkosten seit dem Gewicht von B < -> zu verringern) C ist negativ).

Jetzt die Frage: ist es möglich, solche Schleifen zu vermeiden? Ich habe keine Option in der API gefunden. Die isAllowingLoops() -Methode des Graph-Objekts gibt "false" zurück.

Können Sie mir einen Hinweis geben, was ich hier tun soll?

Vielen Dank im Voraus!

Answer 1

die Grafik Constructing wie folgt geben Sie den Pfad Sie suchen:

DefaultDirectedWeightedGraph<String, DefaultWeightedEdge> g; 
g = new DefaultDirectedWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class); 

g.addVertex("a"); 
g.addVertex("b"); 
g.addVertex("c"); 
g.addVertex("d"); 

DefaultWeightedEdge edge1 = g.addEdge("a", "b"); 
g.setEdgeWeight(edge1, 10); 
DefaultWeightedEdge edge1a = g.addEdge("b", "a"); 
g.setEdgeWeight(edge1a, 10); 


DefaultWeightedEdge edge2 = g.addEdge("a", "c"); 
g.setEdgeWeight(edge2, 10); 
DefaultWeightedEdge edge2a = g.addEdge("c", "a"); 
g.setEdgeWeight(edge2a, 10); 


DefaultWeightedEdge edge3 = g.addEdge("b", "c"); 
g.setEdgeWeight(edge3, -1); 
DefaultWeightedEdge edge3a = g.addEdge("c", "b"); 
g.setEdgeWeight(edge3a, -1); 


DefaultWeightedEdge edge4 = g.addEdge("b", "d"); 
g.setEdgeWeight(edge4, 10); 
DefaultWeightedEdge edge4a = g.addEdge("d", "b"); 
g.setEdgeWeight(edge4a, 10); 


List<DefaultWeightedEdge> path = BellmanFordShortestPath.findPathBetween(g, "a", "d"); 
System.out.println(path); 

Die oben AUSGABE:

[(a : c), (c : b), (b : d)]