java - 寻找 DAG 中 2 个顶点之间的最短路径(未加权)

Question

在 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;
}

Answer 1

由于模型中所有边的权重相同，因此您可以使用 BFS搜索找到从 S 到 T 的最短路径。

这是一个迭代过程，从集合 #0 开始，仅包含源节点 ({S})。在每一步 i 中，您通过一步查找集合 (i-1) 中可实现的所有节点来创建集合 #i。

迭代在两种情况下终止:

1) 当你检测到集合 #k 包含 T 时。在这种情况下，你返回 k-1。

2)当集合为空时，表示两个节点不可达。

内存消耗大约是节点数量的两倍，因为在每个步骤 i 中，您都使用两个集合(i-1 和 i)，受节点总数限制。

--编辑--

这是一个可能的实现(我对其进行了一些测试):

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; 
    }
}

该实现假设in和out定义为List []，节点由从0开始的数字标识。最小距离计算为路径中中间节点的数量，而不是边的数量。

列表中的重复项不会破坏任何内容，但它们与算法无关。