1

我写了一个名为的类Adjacency，它读取一个 .txt 文件，其中包含与邻居有距离的不同城市。一些条目的示例是

...
Lede     Alst     7
Alst     Merelbeke     26
Merelbeke     Alst     26
Alst     Ninove     13
Ninove     Alst     13
...

Adjacency大约有 130 行代码，我可以根据要求粘贴。现在，一旦运行，它会在命令中打印出以下几行

...
Lebbeke --> Aalst[14.0], Asse[12.0], Buggenhout[6.0]
Aalter --> Aalst[49.0], Asse[63.0]
...

这只是从 Lebbeke 和 Aalter 到他们的邻居的距离。我现在想将此结果与 Dijkstras 算法一起使用HashMap，以便仅从输入start节点和stop节点中找到最近的路径。

我见过很多使用 Dijkstras 算法的例子，但他们只使用整数作为节点，但我希望节点能够HashMap用于查找节点。

我的想法是这样的：

我创建了一个HashMap，其中每个键都是节点，每个值都是包含所有邻居的ArrayList（或）。List此外，在所有教程中，他们以无穷大启动起始节点，0其余节点以无穷大启动。但是，由于我事先不知道有多少未访问的节点，（因为我将读取每个节点数量不同的文件）我无法将它们初始化为无穷大。我应该将它们初始化为什么？只是一个很大的数字？

在我的类 PathFinder 中，我有我想要实现的方法 Dijkstra。

public class PathFinder<Node> {

    private DirectedGraph<Node> graph;
    private long startTimeMillis;

    public PathFinder(DirectedGraph<Node> graph) {
        this.graph = graph;
    }

    public class Result<Node> {
        public final boolean success;
        public final Node start;
        public final Node goal;
        public final double cost;
        public final List<Node> path;
        public final int visitedNodes;
        public final double elapsedTime;

        public Result(boolean success, Node start, Node goal, double cost, List<Node> path, int visitedNodes) {
            this.success = success;
            this.start = start;
            this.goal = goal;
            this.cost = cost;
            this.path = path;
            this.visitedNodes = visitedNodes;
            this.elapsedTime = (System.currentTimeMillis() - startTimeMillis) / 1000.0;
        }

        public String toString() {
            String s = "";
            s += String.format("Visited nodes: %d\n", visitedNodes);
            s += String.format("Elapsed time: %.1f seconds\n", elapsedTime);
            if (success) {
                s += String.format("Total cost from %s -> %s: %s\n", start, goal, cost);
                s += "Path: " + path.stream().map(Object::toString).collect(Collectors.joining(" -> "));
            } else {
                s += String.format("No path found from %s", start);
            }
            return s;
        }
        public Result<Node> search(String algorithm, V start, V goal) {
            startTimeMillis = System.currentTimeMillis();
            switch (algorithm) {
            case "random":   return searchRandom(start, goal);
            case "dijkstra": return searchDijkstra(start, goal);
            case "astar":    return searchAstar(start, goal);
           }
        throw new IllegalArgumentException("Unknown search algorithm: " + algorithm);
        }

   public Result<Node> Dijkstra(Node start, Node goal) {

      int visitedNodes = 0;
      Node current = start;

      ArrayList<Double> distanceToNeighbour = new ArrayList<Double>();
      distanceToNeighbour.add(/*Here I need to find the neigbours, get the distances and put them in*/);

      HashMap<Node, ArrayList<Double>> nodesToCosts = new HashMap<Node, ArrayList<Double>>();
      nodesToCosts.put(/*Here I need to loop through all the nodes and put one at a time*/, distanceToNeighbour)

      // ... and then I proceed with the algorithm here.

      return new Result<>(false, start, null, -1, null, visitedNodes);
    }
}

所以你可以看到我的问题归结为两件事：

  1. 如何从 Adjacency 获取节点并将它们作为键放在我的 HashMap 中？
  2. 如何找到所有节点的所有邻居并找到它们的距离？（这些实际上是我想放入ArrayList对应于每个键/节点的图的边缘。）

欢迎任何关于良好开端的帮助。在此之后，我相信我可以自己完成算法。如果我的问题不好，请给我反馈如何改进它。

4

1 回答 1

0

对于您的第一个问题，您逐行读取文件以获取三个数据：

StartCity, Neighbor, Distance

将这三条信息标记化，并用StartCityas添加到 hashmap 中Key。您将需要一些结构来保存 [Neighbor, Distance] 的 2 元组。Value你的将HashMap是一个List<2-tuple>.

于 2019-12-10T20:42:42.407 回答