- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
JGraphT有许多最短路径的实现(Dijkstra、Belman Ford 等)
我需要一个未加权图的单源最短路径。
这是我的问题(特定于 JGraphT):
首先,我假设对未加权的图使用 Dijkstra 是一种浪费(使用优先级队列,它的队列双端队列比 BFS 使用的常规队列慢,并且由于在未加权的图上所有权重都是 1,这不是真的添加任何值)。我的假设正确吗?
假设 1 的答案是"is",那么我假设我将使用 BreadthFirstIterator
而不是滚动我自己的,(经过单元测试,并且作为简单的 BFS,我是当然我会有一些极端案例错误,即使是 Java 的二进制搜索也有整数溢出,这要归功于 Josh Bloch 自己引入的错误,直到 2006 年才解决!)。但问题是,从原始 BFS 到实际获得单源最短路径还有一个(非常小的)步骤,我应该编写自己的 UnweightedSingleSourceShortestPaths
类吗?或者是否有一个隐藏在 JGraphT 核心库中的,我可以直接插入?
最佳答案
因为我认为我找到了第二个问题的答案,我认为它也回答了第一个问题(如果 JgraphT 的 Dijkstra 对于所有权重 = 1 的简单情况最有效,那么为什么 CDK 会创建自己的?)
这是 #2 的答案 - 是的,有一个开源 (LGPL) 解决方案:https://github.com/cdk/cdk/blob/master/legacy/src/main/java/org/openscience/cdk/graph/BFSShortestPath.java
关于java - JGraphT 中未加权图的单源最短路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30462107/
在 jgrapht 中,我添加了一些顶点。 我想知道如何获取我已添加或已存在于 jgrapht 中的所有顶点? 有办法得到吗? 最佳答案 这将给出图中的所有顶点。 DefaultDirectedGra
在 jgrapht 中,我添加了一些顶点。 我想知道如何获取我已添加或已存在于 jgrapht 中的所有顶点? 有办法得到吗? 最佳答案 这将给出图中的所有顶点。 DefaultDirectedGra
我正在 jgrapht 中寻找一个允许我构建图表的类动态地并在运行时在给定图中生成新边 基于算法分支的时间。 我需要实现分支定界算法 我看到这个类ListenableDirectedWeightedG
方法 getSource()和 getTarget() org.jgrapht.graph.DefaultEdge 上的 DefaultEdge 受到保护。 我应该如何访问 edgeSet() 返回的
SimpleWeightedGraph g = new SimpleWeightedGraph<>(DefaultWeightedEdge.class); String v1 = "v1";
我正在构建一个关于图论算法的项目,为此我使用 JGraphT .我已经完全构建了我的图表,并且在过去的几个月里我一直在研究它。现在我想导出它,以便在 Gephi 中可视化它。我不想使用 JGraph
我有一个问题,本质上可以看作是一个图表。我正在考虑使用 JGraphT 来实现它,而不是自己动手。使用 JGraphT 从图中获取最小生成树的最佳方法是什么? 最佳答案 不幸的是,我不知道足够的图论来
除了我正在使用的 JGraphT (Java) 库之外,我还是图论新手,以便实现我正在尝试解决的物流问题的解决方案。因此,我对解决这个问题的最佳方法有点迷失,我必须在给定传入数据的情况下表示 carg
假设我有以下两个树形图: a i / \ / \ b
我正在使用SimpleDirectedWeightedGraph来自JGrapghT 1.2.0图书馆。我的目标是在顶点 A 之间创建两条边和B这样A B 。如果我这样做: graph.addEdg
我正在尝试遍历所有节点,因此我可以将它们打印出来用于 graphviz。使用 JGraphT 库执行此操作的最佳方法是什么? public static void main(String[] args
我有制作无向图的代码: UndirectedGraph g = new SimpleGraph(DefaultEdge.class); g.addVertex("1"); g.addVertex("2
我使用以下方法创建了一个有向图: public static DirectedGraph directedGraph = new DefaultDirectedGraph(DefaultEdg
以下是使用 Dijkstra 算法查找最短路径的示例代码: public static void main(String args[]) { SimpleDirectedWeightedGra
我使用 JGraphT 构建了以下图表 A->B graph = new DirectedPseudograph<>(Edge.class); DijkstraShortestPath sho
我有一个简单的无向图 G = (V, E)。给定一个节点 n,是否有一种简单的方法可以找到它的所有邻居,即所有节点 m,使得 {n, m} 在 E? 有 edgesOf 方法,它返回连接到给定节点的所
我想使用 JGraphT 库制作图形。我的代码如下: private UndirectedGraph graph; private HashMap vertixList; public MapGra
希望你一切顺利!我正在尝试编写一个程序,在该程序中我需要创建一个动态加权图并获得从一个顶点到另一个顶点的最短路径。但运行程序后我得到这个异常: run: TEST1 TEST Vertex Add E
我看到了 jgraph 和 jgrapht 的示例,很容易理解,但现在确定我将如何使用 CompleteBipartiteGraph?如何使用语法来实例化图表? http://jgrapht.org/
JGraphT有许多最短路径的实现(Dijkstra、Belman Ford 等) 我需要一个未加权图的单源最短路径。 这是我的问题(特定于 JGraphT): 首先,我假设对未加权的图使用 Dijk
我是一名优秀的程序员,十分优秀!