JGraphT - appliquer BFS à WeightedGraph

Question

J'ai écrit le code de trouver le chemin optimal pour un graphe pondéré:

SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph = 
       new SimpleDirectedWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class); 
graph.addVertex("1"); 
graph.addVertex("2"); 
graph.addVertex("3"); 
graph.addVertex("4"); 
graph.addVertex("5"); 

DefaultWeightedEdge e1 = graph.addEdge("1", "2"); 
graph.setEdgeWeight(e1, 5); 
DefaultWeightedEdge e2 = graph.addEdge("2", "3"); 
graph.setEdgeWeight(e2, 10); 
DefaultWeightedEdge e3 = graph.addEdge("2", "4"); 
graph.setEdgeWeight(e3, 2); 
DefaultWeightedEdge e4 = graph.addEdge("4", "5"); 
graph.setEdgeWeight(e4, 2); 
DefaultWeightedEdge e5 = graph.addEdge("5", "3"); 
graph.setEdgeWeight(e5, 2); 

System.out.println("Shortest path from vertex 1 to vertex 3:"); 
List shortest_path = DijkstraShortestPath.findPathBetween(graph, "1", "3"); 
System.out.println(shortest_path); 

Il retourne le bon, chemin le plus court: 1->2->4->5->3. Mon problème maintenant est - pour le même graphique, je veux obtenir le chemin contenant le plus petit nombre de transferts entre les sommets (dans ce cas ce serait 1->2->3). Pour ce cas d'utilisation, le BFS serait la solution parfaite. Existe-t-il un moyen d'utiliser en quelque sorte le BreadthFirstIterator de JGraphT API ou dois-je écrire un algorithme par moi-même?

Answer 1

La solution la plus simple serait d'ignorer chacun des poids de bord et de calculer le plus court chemin selon l'algorithme de Dijkstra.

Il est possible de créer un graphe orienté non pondéré à partir d'un graphe orienté pondéré avec la classe AsUnweightedDirectedGraph. Cela remplace simplement la méthode getEdgeWeight pour chaque tronçon et renvoie 1.0, c'est-à-dire le poids par défaut.

Graph<String, DefaultWeightedEdge> unweightedGraph = new AsUnweightedDirectedGraph<>(graph); 
List<DefaultWeightedEdge> path = DijkstraShortestPath.findPathBetween(unweightedGraph, "1", "3"); 
System.out.println(path); // prints [(1 : 2), (2 : 3)] 

Ceci peut ne pas fournir les meilleures performances. Pour l'améliorer, vous pouvez créer votre propre BreadthFirstIterator pour simplement parcourir le graphique. Ce code est basé sur this class, mais mis à jour pour correspondre aux versions les plus récentes de JGraphT. Il fournit une classe BFSShortestPath qui trouve le chemin le plus court entre deux sommets avec un BFS, quel que soit le poids sur chaque bord.

public class Test { 

    public static void main(String[] args) { 
     SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph = 
       new SimpleDirectedWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class); 
     graph.addVertex("1"); 
     graph.addVertex("2"); 
     graph.addVertex("3"); 
     graph.addVertex("4"); 
     graph.addVertex("5"); 

     DefaultWeightedEdge e1 = graph.addEdge("1", "2"); 
     graph.setEdgeWeight(e1, 5); 
     DefaultWeightedEdge e2 = graph.addEdge("2", "3"); 
     graph.setEdgeWeight(e2, 10); 
     DefaultWeightedEdge e3 = graph.addEdge("2", "4"); 
     graph.setEdgeWeight(e3, 2); 
     DefaultWeightedEdge e4 = graph.addEdge("4", "5"); 
     graph.setEdgeWeight(e4, 2); 
     DefaultWeightedEdge e5 = graph.addEdge("5", "3"); 
     graph.setEdgeWeight(e5, 2); 

     System.out.println(BFSShortestPath.findPathBetween(graph, "1", "3")); 
    } 

} 

final class BFSShortestPath { 

    private BFSShortestPath() {} // ensure non-instantiability. 

    public static <V, E> List<E> findPathBetween(Graph<V, E> graph, V startVertex, V endVertex) { 
     MyBreadthFirstIterator<V, E> iter = new MyBreadthFirstIterator<>(graph, startVertex); 
     while (iter.hasNext()) { 
      Object vertex = iter.next(); 
      if (vertex.equals(endVertex)) { 
       return createPath(iter, endVertex); 
      } 
     } 
     return null; 
    } 

    private static <V, E> List<E> createPath(MyBreadthFirstIterator<V, E> iter, V endVertex) { 
     List<E> path = new ArrayList<E>(); 
     while (true) { 
      E edge = iter.getSpanningTreeEdge(endVertex); 
      if (edge == null) { 
       break; 
      } 
      path.add(edge); 
      endVertex = Graphs.getOppositeVertex(iter.getGraph(), edge, endVertex); 
     } 
     Collections.reverse(path); 
     return path; 
    } 

    private static class MyBreadthFirstIterator<V, E> extends BreadthFirstIterator<V, E> { 

     public MyBreadthFirstIterator(Graph<V, E> g, V startVertex) { 
      super(g, startVertex); 
     } 

     @Override 
     protected void encounterVertex(V vertex, E edge) { 
      super.encounterVertex(vertex, edge); 
      putSeenData(vertex, edge); 
     } 

     @SuppressWarnings("unchecked") 
     public E getSpanningTreeEdge(V vertex) { 
      return (E) getSeenData(vertex); 
     } 

    } 
}