1

我在为我的 Dijkstra 算法保持最短路径正确时遇到问题。它正确地找到最短的长度并将其返回（使用实际输出验证正确使用的算法），但正在制作的数组不正确。我相信当我更新arraylist时可以找到这个问题。我的代码如下：

public static Double Dijkstras(String startVertexName,
        String endVertexName, ArrayList<String> shortestPath) {
    HashSet<String> S = new HashSet<String>();
    HashMap<String, String> temp = new HashMap<String, String>();
    HashMap<String, Double> cost = new HashMap<String, Double>();
    cost.put(startVertexName, 0.0);
    for (String e : dataMap.keySet()) {
        if (e.compareTo(startVertexName) != 0) {
            cost.put(e, Double.MAX_VALUE);
        }
    }
    while (!S.containsAll(dataMap.keySet())) {

        ArrayList<String> notInS = new ArrayList<String>();
        for (String x : dataMap.keySet()) {
            if (!S.contains(x)) {
                notInS.add(x);
            }
        }
        Double smallest = Double.MAX_VALUE;
        String foundK = "this is not right";
        for (String k : notInS) {
            if (cost.get(k) < smallest) {
                smallest = cost.get(k);
                foundK = k;
            }
        }
        S.add(foundK);
        notInS.remove(foundK);
        HashSet<String> notInSAdjacent = new HashSet<String>();
        for (String g : adjacencies.get(foundK).keySet()) {
            if (notInS.contains(g)) {
                notInSAdjacent.add(g);
            }
        }
        String temp2 = "";
        for (String j : notInSAdjacent) {
            if ((cost.get(foundK) + adjacencies.get(foundK).get(j)) < cost
                    .get(j)) {
                cost.put(j,
                        cost.get(foundK) + adjacencies.get(foundK).get(j));
                temp2 = j;
            }
        }
        if (!temp.containsKey(temp2)) {
            shortestPath.add(foundK);
        } else {
            int index = shortestPath.indexOf(temp.get(temp2));
            shortestPath.remove(index);
            shortestPath.add(index, foundK);

        }
        temp.put(temp2, foundK);

        if (foundK.compareTo(endVertexName) == 0) {
            break;
        }

    }
    return cost.get(endVertexName);

}

让我知道是否有人可以看到明显的错误。如果需要，我可以提供样本输入和输出。谢谢！

4

0 回答 0