1

在 Floyd–Warshall/Dijkstra 回复洪水到来之前，请让我解释一下情况，因为我确信任何一种算法都可以针对这种情况进行调整，并且必须如此，因为这不是一个玩具示例程序（请注意，在 java所以必须保持它在内存方面的可管理性）

我所拥有的是从节点 0 到节点 n 生成的网络图，节点 3 无法链接到节点 5，因为当节点 3 选择它的外链接时节点 5 不存在。每个“节点”都表示为 in_neighbours[nodeID] 和 out_neighbours[nodeID] 表示 nodeId=3，所以我们谈论的是节点 3。还要注意 in_/out_ 都已排序，（in_ 自然排序为 5 将选择它的 out 链接一次全部，只有这样 6 才会选择 out_links，因此 3 的 in_ 永远不能包含 {6, 5, 7}) 并且 ofc 都可以包含重复项。（in/out 是大小为 n 的 ArrayList 数组，其中 out_ 的大小始终为 d 或 m，与 n 一起由用户在启动时指定）

没有重量。我必须做的是找到averageDistance()

public double getAvgDistance() {
    int sum = 0;        

    for (int i=1; i<n; i++) {
        for (int j=0; j < i; j++) {
            sum += dist(i, j);             // there are duplicates, make sure i skip 
        }
    }

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

到目前为止，我所拥有的是最好的情况。注意我只想找到 j & i 之间的距离，而不是同时找到所有距离（内存不足，将在 m=20 d=1 000 000 时进行测试）

private int dist(int i, int j) {
    int dist = 0;

    for (int link : in_neighbours[j]) {
        System.out.print("\nIs "+j+" linked to by "+i);
        if (out_neighbours[i].contains(link)) {
            System.out.print(" - yes!");
            dist = 1;
        }
    }

    return dist;
}

所以我问如果“更新鲜”（ofc 此时图表已完成）节点 i 是否直接链接到它的任何老伙伴，如果是这样，距离是 1 跳。

如果节点向后遍历，它只是我还是“最短”路径将始终是第一个找到的路径？

我如何检查它是否不是 1，基本情况之后的“else”？我的数学相当薄弱，请温柔:) 任何提示如何利用链接已排序的事实？

这不是家庭作业或我试图欺骗的东西，它与代码本身无关，这必须是一个有用的工具，“学习”是一路走来的。

以下是图的外观 nodeID，out links，in links for m=7 n=13，（注意 0 个周期就是图的初始化方式）：

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

抱歉读了这么久。 编辑：方法中的代码错误，这是我现在认为正确的。

修改 dist nr2，试试看是否有路径：

private int dist(int i, int j) {
    int dist = 0, c = 0, count = 0;
    boolean linkExists = false;

    for (int link : in_neighbours[j]) {

        //System.out.print("\nIs "+j+" linked to by "+i);
        if (out_neighbours[i].contains(link)) {

            //System.out.print(" - yes!");
            dist = 1; // there is a direct link

        } else {

            while ( c < j ) {
                // if there's a path from 0 up to j, check if 'i' links to a node which eventually links to 'j'
                if (out_neighbours[i].contains(c) && 
                        (out_neighbours[c].contains(link) || in_neighbours[c].contains(link) )) {

                    count++; // yes. and this is one node we had to step through to get closer
                    linkExists = true;
                } else {
                    linkExists = false; // unreachable, the path was interrupted somewhere on the way
                    break;
                }
                c++; 
            }

            if (linkExists) {
                dist = count-1; // as 2 nodes are linked with 1 edge
            } else {
                dist = 0; // no path was found
            }
        }


    }

    return dist;
}
4

1 回答 1

2

Since all edges have the same weight in your model, you can use a BFS search to find the shortest path from S to T.

This is an iterative process, starting with set #0, containing only the source node ({S}). At each step i, you create set #i by finding all nodes achievable from set (i-1) in one step.

The iteration terminates in two cases:

1) When you detect that set #k contains T. In this case you return k-1.

2) When the set is empty, meaning that the two nodes are unreachable.

The memory consumption is about twice the number of nodes, since at each step i you are working with two sets (i-1 and i), bounded by the total number of nodes.

--EDIT--

Here is a possible implementation (I made some tests on it):

private Integer getDist(int i, int j) {
    Set<Integer> currentSet = new HashSet<Integer>();
    currentSet.add(i);
    int dist = 0;
    while (true) {
        Set<Integer> nextSet = new HashSet<Integer>();
        for (Integer currNode : currentSet)
            nextSet.addAll(out[currNode]);

        if (nextSet.isEmpty())
            return null; //i.e. infinite
        if (nextSet.contains(j))
            return dist;
        dist++;
        currentSet = nextSet; 
    }
}

The implementation assumes that in and out are defined as List<Integer>[], and nodes are identified by numbers starting from 0. The minimal distance is counted as the number of intermediate nodes in the path, and not as the number of edges.

The duplicates you have in the lists do not break anything here, but they are irrelevant for the algorithm.

于 2010-06-30T14:57:12.090 回答