1

该图未加权，HashSets neighbours[] 数组的一个元素是节点 neighbours[1] 是节点 1（它们从 0 开始，请注意），其唯一的相邻节点为 2 3 4 5。（所以 neighbours[5]将包含 1)。我有以下方法，我做了很多帮助，因为我没有得到超出理论的算法。它返回的数字应该是图中 2 个节点之间的平均距离。

想象一下，我有以下图表（节点：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);
}

我在铸造或打印实数方面没有太多经验，所以我希望这与这些有关！欢迎大家评论

4

3 回答 3

1

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

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

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

于 2010-07-11T14:24:39.843 回答
0

我不确定我是否完全理解您的问题，但听起来您可能会遇到问题，因为您打印的价值不完全符合您的预期。我怀疑问题可能出在您打印双精度值时。每当您将 double 直接转换为 String 时，我知道您会得到意想不到的结果。

这篇文章建议使用 BigDecimal 而不是 double 来保持精度： Retain precision with double in Java

因此，也许尝试执行以下操作，看看是否有更好的结果。

BigDecimal.valueOf(<your double value here>).toPlainString();
于 2010-07-09T16:30:17.063 回答
0

我只是猜测，但我偶尔会看到距离设置为Integer.MAX_VALUE. 如果这些数字实际上输入了结果，然后除以 10 的一个或两个因子，那将很好地解释为什么平均值比预期的要大得多，并且与 MAX_VALUE 大致相同。

当用于确定备选方案中的最短路径时，可以在图表中使用这个大值，但是一旦达到确定实际距离的地步，该数字就必须消失！

要么你的路径长度在 MAX_VALUE 的范围内，这表示没有路径。因此，该路径长度不会进入您的平均值。或者你的路径长度是一个与你的图中距离相同大小的小整数，那么它是有效的，你可以将它包含在你的计算中。

从中吸取的教训：仅仅因为一个数字来自计算机程序，并不意味着它是值得信赖或正确的！

于 2010-07-11T14:33:55.343 回答