Дейкстры — Очередь

Я использую следующий код для алгоритма Дейкстры:

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

Спасибо!

2

Решение

Да. Пожалуйста, проверьте Стандартную библиотеку шаблонов для этого и многих других классов коллекции.

Вот ссылка:
http://www.cplusplus.com/reference/queue/queue/

2

Другие решения

priority_queue хорошо подходит для алгоритма Дейкстры и уменьшает сложность алгоритма во время выполнения (по сравнению с обычной очередью)

3

На ум приходит как минимум три вещи:

  1. станд :: Deque — двусторонняя очередь.
  2. станд :: очереди — адаптер контейнера очереди.
  3. станд :: priority_queue Приоритетная очередь.

Есть также другие контейнеры и алгоритмы, которые можно найти в C ++ Standard Library.

1
По вопросам рекламы [email protected]