关于JGraphT中Dijkstra算法是否支持加权图最小权重路径的咨询

JGraphT的DijkstraShortestPath实现完全支持加权图，默认就会以边的权重作为路径代价计算，直接就能拿到顶点a到b的最小权重路径，不用额外做特殊配置。

具体实现步骤 #

• 创建加权图实例
  用DefaultWeightedGraph（无向）或DefaultDirectedWeightedGraph（有向）来构建加权图，指定边类型为DefaultWeightedEdge：

  // 示例：创建无向加权图
  Graph<String, DefaultWeightedEdge> weightedGraph = new DefaultWeightedGraph<>(DefaultWeightedEdge.class);
  

• 添加顶点与带权重的边
  先添加顶点，再添加边并设置权重（默认边权重为1.0，建议手动指定）：

  // 添加顶点
  weightedGraph.addVertex("a");
  weightedGraph.addVertex("b");
  weightedGraph.addVertex("c");
  
  // 添加边并设置权重
  DefaultWeightedEdge aToC = weightedGraph.addEdge("a", "c");
  weightedGraph.setEdgeWeight(aToC, 2.5); // a到c的权重为2.5
  DefaultWeightedEdge cToB = weightedGraph.addEdge("c", "b");
  weightedGraph.setEdgeWeight(cToB, 3.0); // c到b的权重为3.0
  DefaultWeightedEdge aToB = weightedGraph.addEdge("a", "b");
  weightedGraph.setEdgeWeight(aToB, 7.0); // a到b的直接边权重为7.0
  

• 调用Dijkstra算法计算最小权重路径
  用findPathBetween获取路径，getPathWeight获取路径总权重：

  // 获取a到b的最小权重路径
  List<DefaultWeightedEdge> shortestPath = DijkstraShortestPath.findPathBetween(weightedGraph, "a", "b");
  // 获取路径总权重
  double totalWeight = DijkstraShortestPath.getPathWeight(weightedGraph, "a", "b");
  
  // 输出结果
  System.out.println("a到b的最小权重路径：");
  for (DefaultWeightedEdge edge : shortestPath) {
      String source = weightedGraph.getEdgeSource(edge);
      String target = weightedGraph.getEdgeTarget(edge);
      double weight = weightedGraph.getEdgeWeight(edge);
      System.out.printf("%s -> %s (权重：%.1f)%n", source, target, weight);
  }
  System.out.printf("路径总权重：%.1f%n", totalWeight);
  

注意点 #

• 若使用有向加权图，只需把DefaultWeightedGraph换成DefaultDirectedWeightedGraph，算法逻辑完全一致。
• 务必确认边的权重已正确设置，未手动设置的边会默认使用1.0作为权重，可能影响计算结果。

内容的提问来源于stack exchange，提问作者Gábor Szegedi