2

ダイクストラのアルゴリズムには次のコードを使用します。

int Graph::ShortestPath(Vertex *start, Vertex *end)
{
    int posStart = IndexOfNode(start);
    int posEnd = IndexOfNode(end);
    int result;

    bool visit[cntNodes];
    int distance[cntNodes];
    // Initialization: set every distance to -1 until we discover a path
    for (int i = 0; i < cntNodes; i++) {
        visit[i] = false;
        distance[i] = -1;
    } // for

    // The distance from the source to the source is defined to be zero
    distance[posStart] = 0;

    Queue *q = new Queue(maxNodes);
    q->Enqueue(posStart);
    while (!q->Empty()) {
        int next, alternative;
        q.Dequeue(next);
        for (int i = 0; i < cntNodes; i++) {
            if (adjmatrix[next][i]) {
                alternative = distance[next] + adjmatrix[next][i];
                if (visit[i]) {
                    if (alternative < distance[i]) {
                        distance[i] = alternative;
                        q.Enqueue(i);
                    } // if
                }// if
                else {
                    distance[i] = alternative;
                    visit[i] = true;
                    q.Enqueue(i);
                } // else
            } // if
        } // for
    }
    delete q;
    result = distance[posEnd];
    delete[] visit;
    delete[] distance;
    return result;
}

現在、Queue と呼ばれる独自に作成したクラスを使用しています。

Queue *q = new Queue(maxNodes)

独自の実装の代わりに使用できる C++ 標準キューはありますか。

この機能だけが必要です：

Queue *q = new Queue(maxNodes);
q->Enqueue(posStart);
    q.Dequeue(next);

ありがとう！

4

3 に答える 3

3

priority_queueは Dijkstraのアルゴリズムに適しており、(通常のキューと比較して) アルゴリズムの実行時の複雑さを軽減します。

于 2012-12-11T20:10:18.980 に答える
2

はい。これと他の多くのコレクション クラスについては、標準テンプレート ライブラリを確認してください。

ここにリンクがあります: http://www.cplusplus.com/reference/queue/queue/

于 2012-12-11T20:06:28.527 に答える
1

頭に浮かぶことは少なくとも3つあります。

  1. std :: deque —両端キュー。
  2. std::queue-キューコンテナアダプタ。
  3. std :: priority_queue —優先キュー。

C++標準ライブラリにある他のコンテナとアルゴリズムもあります。

于 2012-12-11T20:11:53.863 に答える