1

Floyd–Warshall/Dijkstra の返信が殺到する前に、状況を説明させてください。どちらのアルゴリズムもこのケースに合わせて調整できると確信しているためです。そのため、メモリの観点から管理しやすくする必要があります）

私が持っているのは、ノード 0 からノード n まで生成された Web グラフです。ノード 3 はノード 5 にリンクできません。すべての「ノード」は in_neighbours[nodeID] および out_neighbours[nodeID] として表され、nodeId=3 と言うので、ノード 3 について話していることになります。また、in_/out_ は両方ともソートされていることに注意してください (5 が選択されるため、in_ は自然にソートされます)。一度にすべてのリンクをアウトし、その場合にのみ 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;
}

したがって、「より新しい」（この時点でグラフが完成している）ノードiが古い仲間のいずれかに直接リンクしているかどうかを尋ねています。そうであれば、距離は1ホップです。

それは私だけですか、それともノードが後方にトラバースされた場合、「最短」パスが常に最初に見つかったパスになりますか?

基本ケースの後の「else」である 1 でないかどうかを確認するにはどうすればよいですか? 私の数学はかなり弱いです 優しくしてください:) リンクがソートされているという事実を利用するためのヒントはありますか?

それは宿題でも、ごまかそうとしているものでもなく、コード自体の問題でもありません。これは便利なツールでなければなりません。「学習」は途中で自然に行われます。

m=7 n=13 のノード ID、アウト リンク、イン リンクでグラフがどのように見えるかを次に示します (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  |

長々と読んで辛くてすみません。 EDIT：メソッドのコードが間違っています。これは私が今正しいと思うものです。

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

モデル内のすべてのエッジの重みが同じであるため、BFS検索を使用して S から T への最短経路を見つけることができます。

これは、ソース ノード ({S}) のみを含むセット #0 から始まる反復プロセスです。各ステップ i で、1 つのステップでセット (i-1) から達成可能なすべてのノードを見つけることによって、セット #i を作成します。

反復は次の 2 つの場合に終了します。

1) セット #k に T が含まれていることを検出した場合。この場合、k-1 を返します。

2) セットが空の場合、2 つのノードに到達できないことを意味します。

各ステップ i で 2 つのセット (i-1 と i) を使用し、ノードの総数によって制限されるため、メモリ消費量はノード数の約 2 倍になります。

- 編集 -

これが可能な実装です（私はいくつかのテストを行いました）：

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<Integer>[] として定義され、ノードが 0 から始まる番号で識別されることを前提としています。最小距離は、エッジの数ではなく、パス内の中間ノードの数としてカウントされます。

リストにある重複は、ここでは何も壊しませんが、アルゴリズムには関係ありません。

于 2010-06-30T14:57:12.090 に答える