实施 Dijkstra 算法的问题

Question

我正在尝试解决一个问题，我需要找到图中两点之间的最大距离。我编写这段代码是为了实现 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];
}

Answer 1

首先，Dijkstra算法求的是最短路径，所以应该是minDistance，而不是maxDistance。

接下来，要实现广度优先搜索，需要一个有序的数据结构。您的 bfsQueue 目前只是一个 LinkedList。使用链接列表，您可以按插入顺序迭代项目。但在 Dijkstra 的算法中，始终处理下一个最近的邻居很重要。因此通常使用优先级队列来实现。

举个例子，为什么这会产生影响：你想从 A 到 B 的图像。有两条路线可用，一条长的路线由两条边组成，另一条较短的路线由 4 条边组成。在您的情况下，您基本上是通过图形从一开始就按边数扩展，而不是按距离扩展。所以你会首先找到由两条边组成的路线，即使这是较慢的一条。

如果您使用 PriorityQueue，请注意，像您当前所做的那样减少邻居的 distance/priority (if (newLength > distance[neighbor]) { distance[neighbor] = newLength; }) 将不起作用，因为优先级队列将不起作用自动重新排序。您必须先从优先级队列中删除邻居，更新距离，然后将其重新插入优先级队列，以便将其排序到正确的位置。

实施 Dijkstra 算法的问题

Issue in Implementing Dijkstra's algorithm

java

dijkstra