java - 使用 Dijkstra (java) 得出的平均距离结果不正确

Question

该图未加权，HashSets neighbours[]数组的一个元素是一个节点neighbours[1] 是节点 1(请注意，它们从 0 开始)，其独特的邻居节点为 2 3 4 5。(因此 neighbours[5] 将包含 1)。我在得到很大帮助的情况下采用了以下方法，因为我没有得到超出理论的算法。它返回的数字应该是图中两个节点之间的平均距离。

假设我有以下图表(节点:in_links | out_links；neighbours[] 不包含节点 0 处的 0 个循环，并且正如我所说，没有重复项。)

0: 0 0 0 | 0 0 0 1 1 1 2 3 5 6 7 7 8 8 9 9 11 
1: 0 0 0 | 2 2 3 4 4 5 6 8 
2: 0 1 1 | 3 
3: 0 1 2 | 4 9 
4: 1 1 3 | 5 12 
5: 0 1 4 | 6 7 10 
6: 0 1 5 | 10 11 12 
7: 0 0 5 | 
8: 0 0 1 | 10 
9: 0 0 3 | 12 
10: 5 6 8 | 11 
11: 0 6 10 | 
12: 4 6 9 | 

对于这个简单的图表，返回的距离是 5.781686749230769E8 ?!?!代码:

    public double getAvgDistance() {
    double total = 0;
    int[] dist = new int[n];
    ArrayList<Integer> Q = new ArrayList<Integer>();
    int tmp, index = 0, w = 0;

    for (int u=0; u<n; u++) {
        System.out.print("Avg Dist at "+u+"\r");
        // Initialise Q and dist for this iteration
        for (int v=u+1; v<n; v++) {
            Q.add(v);

            if (neighbours[u].contains(v)) {
                dist[v] = 1;
            } else {
                dist[v] = Integer.MAX_VALUE;
            }
        }

        while (!Q.isEmpty()) {

            tmp = dist[0];
            for (int e=1; e<Q.size(); e++) {
                if (dist[e] < tmp) {
                    w = Q.get(e);
                    tmp = dist[w]; // smallest dist is for this element w so far
                    index = e;
                }
            }
            Q.remove(index);

            for (int z : neighbours[w]) {
                if ( Q.contains(z)
                        && (dist[w]+1 < dist[z]) ) {

                    dist[z] = dist[w]+1;
                }
            }

        } // while end

        for (int v = u+1; v < n; v++ ) {
            total += dist[v];
        }

    } // for 0-n end

    return total /= (double)(n*(n-1)/2);
}

我在类型转换或打印实数方面没有太多经验，所以我希望它与这些有关!欢迎大家评论

Answer 1

如果我正确理解你的问题，节点 7、11 和 12 没有出站链接，因此没有到其他节点的有效路径。

在这些情况下，您的算法是否会通过插入成本为 Integer.MAX_VALUE 的链接来强制路径？如果是这样，那就可以解释为什么平均成本如此之高。

我还想知道评估正向和反向路径是否会更好。在有向图中，路径 AB 的成本不一定与路径 BA 的成本相同。使用当前算法，会计算以节点 12 结束的每条路径的成本，但不会评估从节点 12 开始的路径。