JGraphT - 適用於BFS WeightedGraph

Question

我寫的代碼中發現了加權圖中的最佳路徑：

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); 

它返回正確的，最短路徑：1->2->4->5->3。我現在的問題是 - 對於同一個圖，我想獲得包含頂點之間傳輸數量最少的路徑（在這種情況下，它將是1->2->3）。對於這種使用情況，BFS將是完美的解決方案。有沒有辦法以某種方式使用JGraphT API中的BreadthFirstIterator或者我必須自己編寫算法？

Answer 1

最簡單的解決方案是按照Dijkstra算法忽略每個邊權重並計算最短路徑。

可以使用AsUnweightedDirectedGraph類從加權有向圖創建未加權有向圖。這簡單地覆蓋了每個邊的getEdgeWeight方法並返回1.0，即默認權重。

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

這可能不會提供最佳性能。爲了改進它，你可以建立你自己的BreadthFirstIterator來遍歷圖表。此代碼基於this class，但更新爲與更新版本的JGraphT相匹配。它提供了一個BFSShortestPath類，無論每個邊上的權重如何，都可以在BFS中找到兩個頂點之間的最短路徑。

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); 
     } 

    } 
}