JGraphT - 将 BFS 应用于 WeightedGraph [英] JGraphT - apply BFS to WeightedGraph

问题描述

我已经编写了寻找加权图最佳路径的代码:

I have written the code finding the optimal path for a Weighted Graph:

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 或者我必须自己编写算法?

It returns the correct, shortest path: 1->2->4->5->3. My problem now is - for the same graph, I want to obtain the path containing the fewest number of transfers between vertices (in this case it would be 1->2->3). For this use-case the BFS would be the perfect solution. Is there a way to somehow use the BreadthFirstIterator from JGraphT API or do I have to write an algorithm by myself?

推荐答案

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

The simplest solution would be to ignore each of the edge weights and calculate the shortest path as per Dijkstra's algorithm.

可以使用 从加权有向图创建未加权有向图AsUnweightedDirectedGraph 类.这只是覆盖每个边的 getEdgeWeight 方法并返回 1.0，即默认权重.

It is possible to create an unweighted directed graph from a weighted directed graph with the AsUnweightedDirectedGraph class. This simply overrides the getEdgeWeight method for each edge and returns 1.0, i.e. the default weight.

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 来遍历图形.此代码基于 此类，但已更新以匹配 JGraphT 的最新版本.它提供了一个 BFSShortestPath 类，该类可以找到具有 BFS 的两个顶点之间的最短路径，无论每条边的权重如何.

This might not provide the best performance. To improve it, you can build your own BreadthFirstIterator to just iterate through the graph. This code is based on this class, but updated to match the more recent versions of JGraphT. It provides a BFSShortestPath class that finds the shortest path between two vertices with a BFS, whatever the weight on each edge.

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 应用于 WeightedGraph的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！