Глава 21, Кратчайшие пути. Используя для вычисления SPT очередь с приоритетами вершин (в порядке возрастания их расстояния от источника)

Используя для вычисления SPT очередь с приоритетами вершин (в порядке возрастания их расстояния от источника). Интерфейс очереди с приоритетами совпадает с использованным в программе 20.7 и реализован в программе 20.10.

Конструктор предназначен также для обобщенного поиска на графе и реализует другие алгоритмы PFS с другими назначениями приоритетов для Р (см. рассуждения по тексту раздела). Оператор, присваивающий весам вершин дерева значения 0, необходим для общей реализации PFS, но не для алгоритма Дейкстры, поскольку приоритеты вершин, добавляемых к SPT, являются неубывающими.

template < class Graph, class Edge> class SPT { const Graph & G; vector< double> wt; vector< Edge *> spt; public:

SPT (const Graph & G, int s): G(G),

spt< G.V<)), wt(G.V(), G.V()) { PQi< double> pQ(G.V(), wt);

for (int v = 0; v < G.V(); v++) pQ. insert (v); wt[s] = 0.0; pQ. lower (s); while (! pQ.empty())

{ int v = pQ. getmin (); // wt[v] = 0.0; if (v! = s & & spt[v] == 0) return; typename Graph:: adjIterator A(G, v); for (Edge* e = A.beg();! A.end(); e = A.nxt()) { int w = e-> w();

double P = wt[v] + e-> wt(); if (P < wt[w])

{ wt[w] = p; pQ.lower(w); spt[w] = e; } } } }

Edge *pathR(int v) const { return spt[v]; } double dist(int v) const { return wt[v]; } };

Программа 21.1 является альтернативной реализацией PFS для разреженных графов; она несколько проще, чем программа 20.7, и непосредственно соответствует неформаль­ному описанию алгоритма Дейкстры, данному в начале этого раздела. Она отличается от программы 20.7 тем, что в ней инициируется очередь с приоритетами, содержащая все вершины сети, и она поддерживает эту очередь с использованием сигнальных значений для вершин, которые не лежат ни на дереве, ни на бахроме (невидимые вершины с сиг­нальными значениями). Для сравнения, программа 20.7 содержит в очереди с приорите­тами только вершины, связанные с деревом единственным ребром. Хранение всех вер­шин в очереди упрощает код, но может привести к небольшой потере эффективности для некоторых графов (см. упражнение 21.31).

Общие результаты, рассмотренные в главе 20 и касающиеся производительности по­иска по приоритету (PFS), дают нам определенные сведения об эффективности этих ре­ализаций алгоритма Дейкстры для разреженных графов (программа 21.1 и программа 20.7, с соответствующими изменениями). Для справки мы повторно приводим здесь эти резуль­таты. Поскольку доказательства не зависят от функции вычисления приоритета, они по­вторяются без изменений. Это результаты для наихудшего случая, и они относятся к обе­им программам, хотя программа 20.7 может оказаться более эффективной для многих классов графов, поскольку она поддерживает бахрому меньших размеров.