1

Dijkstra 算法有一个步骤提到“选择具有最短路径的节点”。我意识到这一步是unnecessary if we dont throw a node out of the graph/queue。据我所知,这很有效,没有已知的缺点。这是代码。如果失败,请指导我?如果确实如此,那怎么办?[编辑 => 这段代码已经过测试并且运行良好,但是我的测试用例有可能并不详尽,因此将其发布在 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;
    } 
4

1 回答 1

1

问题 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 差得多,但我会对它在实践中的表现感兴趣。我的猜测是它适用于稀疏的几乎树状图,但不太适用于密集图。

于 2013-10-05T20:40:19.227 回答