java - 修改为Dijkstra，需要验证

dijkstra算法有一个步骤提到“选择路径最短的节点”。我意识到这一步是unnecessary if we dont throw a node out of the graph/queue。据我所知，这很有效，没有已知的缺点。这是密码。如果失败了请告诉我？如果是，那怎么办[EDIT=>这段代码经过测试，运行良好，但我的测试用例可能并不详尽，因此将其发布在STACKOVERFLOW上]

  public Map<Integer, Integer> findShortest(int source) {
        final Map<Integer, Integer> vertexMinDistance = new HashMap<Integer, Integer>();
        final Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(source);
        vertexMinDistance.put(source, 0);

        while (!queue.isEmpty()) {
            source = queue.poll();
            List<Edge> adjlist = graph.getAdj(source);
            int sourceDistance = vertexMinDistance.get(source);

            for (Edge edge : adjlist) {
                int adjVertex = edge.getVertex();
                if (vertexMinDistance.containsKey(adjVertex)) {
                    int vertexDistance = vertexMinDistance.get(adjVertex);
                    if (vertexDistance > (sourceDistance + edge.getDistance())) {
                         //previous bug
                         //vertexMinDistance.put(adjVertex, vertexDistance);
                         vertexMinDistance.put(adjVertex, sourceDistance + edge.getDistance())
                    }
                } else {
                    queue.add(adjVertex);
                    vertexMinDistance.put(adjVertex, edge.getDistance());
                }
            }
        }
        return vertexMinDistance;
    }

最佳答案

问题1
我认为代码中有一个错误，它说：

                int vertexDistance = vertexMinDistance.get(adjVertex);
                if (vertexDistance > (sourceDistance + edge.getDistance())) {
                    vertexMinDistance.put(adjVertex, vertexDistance);
                }

因为这没有效果（adjVertex的vertexMinDistance设置回其原始值）。
最好是这样的：

                int vertexDistance = vertexMinDistance.get(adjVertex);
                int newDistance = sourceDistance + edge.getDistance();
                if (vertexDistance > newDistance ) {
                    vertexMinDistance.put(adjVertex, newDistance );
                }

问题2
您还需要使用以下方法将adjVertex添加到队列中：

                int vertexDistance = vertexMinDistance.get(adjVertex);
                int newDistance = sourceDistance + edge.getDistance();
                if (vertexDistance > newDistance ) {
                    vertexMinDistance.put(adjVertex, newDistance );
                    queue.add(adjVertex);
                }

如果您不这样做，您将得到一个不正确的图形回答，例如：

A->B (1)
A->C (10)
B->C (1)
B->D (10)
C->D (1)

正确的路径是权重3的A->B->C->D，但是如果没有修改，那么我相信您的算法将选择一个较长的路径（因为一旦找到一个较短的路径，它就不会重新检查C）。
高水平反应
通过这些修改，我认为这种方法基本上是正确的，但是你应该小心计算复杂度。
dijkstra只需要循环主循环v次（其中v是图中的顶点数），而您的算法可能需要对某些图进行更多的循环。
你仍然会得到正确的答案，但可能需要更长的时间。
虽然最坏情况的复杂性比Dijkstra要糟糕得多，但我会对它在实践中的表现感兴趣。我的猜测是，对于稀疏的几乎树状图，它会工作得很好，但是对于稠密的图，它就不那么好了。