Dijkstra算法 - 队列

Question

我使用以下代码实现Dijkstra算法：

我使用以下代码实现Dijkstra算法：

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

谢谢！

- MeJ

Answer 1

priority_queue是Dijkstra算法的一个好选择，相比普通队列可以减少算法的运行时间复杂度。

- Cornstalks

Answer 2

是的。请查看标准模板库（STL）以获取此类和其他许多集合类。

以下是链接: http://www.cplusplus.com/reference/queue/queue/

- RonaldBarzell

---

STL这个术语在这个上下文中是不正确的。你所说的是C++标准库。不要混淆STL和标准库——它们是非常不同的。只有那些对此一无所知的招聘人员才会将其列入工作资格要求 :) - user405725

谢谢您的建议，现在我使用： queue<int> q; q.push(posStart); next = q.front(); q.pop(); q.push(i); - MeJ

Answer 3

至少有三件事情值得一提：

1. std::deque — 双端队列。
2. std::queue - 队列容器适配器。
3. std::priority_queue — 优先队列。

C++标准库中还有其他容器和算法可供使用。

- user405725