使用哈希图的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一起使用，以便仅从节点和stop节点start输入中找到最近的路径。

我看过很多使用 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: %dn", visitedNodes);
s += String.format("Elapsed time: %.1f secondsn", elapsedTime);
if (success) {
s += String.format("Total cost from %s -> %s: %sn", 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. 如何从邻接获取节点并将它们作为键放入我的哈希映射中？
2. 如何找到所有节点的所有邻居并找到到它们的距离？(这些实际上是我想放在与每个键/节点对应的ArrayList中的图形边缘。

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

Answer 1

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

StartCity, Neighbor, Distance

标记这三条信息，并添加到哈希图中，StartCity作为Key。 您将需要一些结构来容纳 [邻居，距离] 的 2 元组。您的HashMapValue将是一个List<2-tuple>。