JGraphT

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

returns 正确的最短路径：1->2->4->5->3。我现在的问题是 - 对于同一个图，我想获得包含顶点之间传输次数最少的路径（在本例中为 1->2->3）。对于这个用例，BFS 将是完美的解决方案。有没有办法以某种方式使用 JGraphT API 中的 BreadthFirstIterator 还是我必须自己编写算法？

Answer 1

最简单的解决方案是忽略每条边的权重并根据 Dijkstra 算法计算最短路径。

可以使用 AsUnweightedDirectedGraph class 从加权有向图创建未加权有向图。这简单地覆盖了每个边的 getEdgeWeight 方法和 returns 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 class 可以找到具有 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);
        }

    }
}

JGraphT - 将 BFS 应用于加权图

JGraphT - apply BFS to WeightedGraph

java

graph

breadth-first-search