java - 找到两个点之间的路径

Question

大家好，我有一个数据库，其中包含点到点距离的点数组，看起来像 {1 2 5, 2 3 4 , 3 4 2} 我正在获取数据

        List<Conniction> tempDeal = ConnictionDAO.getInstance().findAll();

然后将其信息迭代到 Lists

List<String> oneid = new ArrayList<String>();
 List<String> twoid = new ArrayList<String>();
 List<String> size = new ArrayList<String>();
 for(Conniction obj: tempDeal){
     if(obj!=null) {

             oneid.add(obj.getOneid());

             twoid.add(obj.getTwoid());
             size.add(obj.getSize());

现在我需要找到点 1 到点 3 之间的距离，它应该是 9 我应该构建哪个函数

Answer 1

如果您只有点和距离信息，您可以创建一个完整的图（即每个节点都连接到其他节点的图）并在此图上运行 Dijkstra。这样，您可以使用中间节点在两个节点之间找到更短的路径。

请注意，这只有在距离不是度量时才有用/有意义。否则，两点之间的直接连接（即它们的距离）总是小于或等于使用中间节点的距离。