使用HashMap的Dijkstras算法-如何插入从邻接图生成的节点？

Question

我写了一个叫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]
...

这只是从勒贝克和阿尔特到他们的邻居的距离。我现在想将此结果与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中的图形的边缘。）

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

Answer 1

对于您的第一个问题，您只需阅读文件，一共有三个数据：

StartCity, Neighbor, Distance

将这三条信息标记化，并以StartCity作为Key添加到哈希图中。您将需要一些结构来容纳[Neighbor，Distance]的2元组。您的Value的HashMap将是List<2-tuple>。