我正在尝试解决一个问题，需要在图中找到两个点之间的最大距离。我编写了这段代码来实现Dijkstra的算法（显然是通过将最小化更改为最大化），但是在某些情况下它似乎不起作用，而且我无法弄清未解决的情况。谁能帮助我指出我的实现中缺少什么，或者某些固有错误吗？
public double maxDistance(int n, int start, int end) {
Map<Integer, List<Integer>> adjacencyList = getAdjacencyList(); // Adj. list in form of HashMap
Map<String, Double> distanceMap = getDistanceMap(); // <Edge, Double> (value is distance)
Queue<Integer> bfsQueue = new LinkedList<>(); // queue to do a BFS
boolean[] visited = new boolean[n];
double[] distance = new double[n];
bfsQueue.add(start);
while (!bfsQueue.isEmpty()) {
int node = bfsQueue.poll();
List<Integer> neighbors = adjacencyList.getOrDefault(node, new ArrayList<>());
for (int neighbor: neighbors) {
if (visited[neighbor]) continue;
bfsQueue.add(neighbor);
double edgeLength = distanceMap.get(new Edge(node, neighbor));
double newLength = distance[node] + edgeLength;
if (newLength > distance[neighbor]) {
distance[neighbor] = newLength;
}
}
visited[node] = true;
}
return distance[end];
}
首先，Dijkstra的算法找到最短路径，因此应该为minDistance，而不是maxDistance。
接下来，要实现广度优先搜索，您需要一个排序的数据结构。您bfsQueue目前只是一个LinkedList。使用链接列表，您可以按插入顺序遍历项目。但是在Dijkstra的算法中，始终处理下一个最近的邻居很重要。因此，通常使用优先级队列来实现。
例如，为什么会有所不同：您要从A到B的图像。有两种路线可用，一条长路线由两个边缘组成，一条短路线由4个边缘组成。在您的情况下，您基本上是按照自起点以来的边数（而不是距离）来展开图形。因此，即使这是较慢的一条，您也将首先找到由两条边组成的路线。
如果您使用PriorityQueue，则会提醒您减少当前邻居的距离/优先级（if (newLength > distance[neighbor]) { distance[neighbor] = newLength; }）将不起作用，因为优先级队列不会自动重新排序。您必须首先从优先级队列中删除邻居，更新距离，然后将其重新插入优先级队列，以便将其分类到正确的位置。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句