jgrapht

Question

这里是用Dijkstra算法寻找最短路径的示例代码：

public static void main(String args[]) {
    SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph = new SimpleDirectedWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class);
    graph.addVertex("vertex1");
    graph.addVertex("vertex2");
    graph.addVertex("vertex3");
    graph.addVertex("vertex4");
    graph.addVertex("vertex5");

    DefaultWeightedEdge e1 = graph.addEdge("vertex1", "vertex2");
    graph.setEdgeWeight(e1, 5);

    DefaultWeightedEdge e2 = graph.addEdge("vertex2", "vertex3");
    graph.setEdgeWeight(e2, 3);

    DefaultWeightedEdge e3 = graph.addEdge("vertex4", "vertex5");
    graph.setEdgeWeight(e3, 6);

    DefaultWeightedEdge e4 = graph.addEdge("vertex2", "vertex4");
    graph.setEdgeWeight(e4, 2);

    DefaultWeightedEdge e5 = graph.addEdge("vertex5", "vertex4");
    graph.setEdgeWeight(e5, 4);

    DefaultWeightedEdge e6 = graph.addEdge("vertex2", "vertex5");
    graph.setEdgeWeight(e6, 9);

    DefaultWeightedEdge e7 = graph.addEdge("vertex4", "vertex1");
    graph.setEdgeWeight(e7, 7);

    DefaultWeightedEdge e8 = graph.addEdge("vertex3", "vertex2");
    graph.setEdgeWeight(e8, 2);

    DefaultWeightedEdge e9 = graph.addEdge("vertex1", "vertex3");
    graph.setEdgeWeight(e9, 10);

    DefaultWeightedEdge e10 = graph.addEdge("vertex3", "vertex5");
    graph.setEdgeWeight(e10, 1);

    System.out.println("Shortest path from vertex1 to vertex5:");
    List<DefaultWeightedEdge> shortest_path = DijkstraShortestPath.findPathBetween(graph,"vertex1", "vertex5");
    System.out.println(shortest_path);
}

是否有可能获得算法已到达并标记为已访问的节点列表？我看到有一个叫做 TraversalListener 的东西，但它看起来只适用于迭代器，比如 BreadthFirstIterator。

Answer 1

使用 DijkstraShortestPath class 似乎没有此功能。这是因为图迭代器中添加了遍历监听器，无法访问DijkstraShortestPath使用的迭代器

因此，唯一的解决方案是将 DijkstraShortestPath 代码复制到新的 class（我们称之为 MyDijkstraShortestPath）并添加遍历侦听器。

首先，您需要创建一个继承自TraversalListenerAdapter的class MyTraversalListener，并覆盖您想要的方法。

class MyTraversalListener<V, E> extends TraversalListenerAdapter<V, E> {
     // override the method you want, like vertexTraversed and edgeTraversed
}

然后，在我们新建MyDijkstraShortestPathclass的构造函数中，需要添加：

ClosestFirstIterator<V, E> iter =
    new ClosestFirstIterator<V, E>(graph, startVertex, radius);
iter.addTraversalListener(new MyTraversalListener<V, E>());

jgrapht - 获取所有遍历节点的列表

jgrapht - get list of all traversed nodes

java

graph