0

PriorityQueueを使用して、グラフの残りの頂点を最短の走査距離順に格納する大学向けのダイクストラアルゴリズムに取り組んでいます。私が使用するコンパレータ：

class DistanceComparator implements Comparator<Integer> {
    int[] dist; 
    public DistanceComparator(int[] d) {
        dist = d;
    }

    @Override
    public int compare(Integer i, Integer j)
    {
        if((dist[i]-dist[j]) < 0) { 
            return -1;
        }
        if((dist[i]-dist[j]) > 0) { 
            return  1;
        }
        return 0;
    }
}

今私が直面している問題は、距離が変化していることです。そのため、キューのコンパレータを頻繁に更新する必要があります。

static PriorityQueue<Integer> refreshQueue(int[] d) {
    Comparator<Integer> comp = new DistanceComparator(d);
    PriorityQueue<Integer> q = new PriorityQueue<Integer>(adj.length, comp);
    for(int i = 0; i < adj.length; i++) {
        q.add(i);
    }
    return q;
}

これでうまくいきますが、必要なランタイムにも負担がかかりますO(num Edges*log(num Vertices))。

コンパレータを毎回調整する必要をなくすにはどうすればよいですか？

4

1 に答える 1

2

Javaでダイクストラのアルゴリズムを実装する従来の方法は、ノードと距離を含む別のクラスを作成することです。

class Dist implements Comparable<Dist> {
  final int vertex;
  final int distance;

  public int compareTo(Dist other) {
    return Integer.compare(distance, other.distance);
  }
}

そしてそれらを優先キューに入れます。

最適ではないパスを反映する古いDistオブジェクトになってしまいますが、それは「最適な」パスをすでに確認した後であるため、優先キューから既に取り出した頂点は無視してください。

基本的に、変更しないでくださいComparator：比較するオブジェクトを変更してください。

于 2012-06-18T02:18:22.000 に答える