dijkstra_shortest_paths() Функциярешает проблему кратчайших путей на взвешенном, ненаправленном или направленном распределенном графе. Существует две реализации распределенного алгоритма Dijkstra, которые предлагают различные компромиссы производительности. Оба доступны черезdijkstra_shortest_paths().(для совместимости с последовательными программами BGL). Распределенные алгоритмы Dijkstra очень похожи на их последовательные аналоги. Здесь выделены только различия; пожалуйста, обратитесь кпоследовательной реализации Dijkstraдля получения дополнительной информации. Наиболее эффективной реализацией для большинства случаев является алгоритмDelta-Stepping.Однако можно использовать и более консервативные методы.Алгоритм Краузера и др.или симметричныйАлгоритм Эйгера Дейкстра.
Все параметрыпоследовательной реализации Dijkstraподдерживаются и имеют по существу одинаковое значение. Распределенные реализации Dijkstra вводят новый параметр, который позволяет выбратьалгоритм Eager Dijkstraи контролировать объем выполняемой работы. Здесь документируются только различия и новые параметры.
The start vertex must be the same in every process.
OUT: predecessor_map(PredecessorMapp_map)
The predecessor map must be a Distributed Property Map or
dummy_property_map, although only the local portions of the map
will be written.
Default:dummy_property_map
UTIL/OUT: distance_map(DistanceMapd_map)
The distance map must be either a Distributed Property Map or
dummy_property_map. It will be given the vertex_distance
role.
IN: visitor(DijkstraVisitorvis)
The visitor must be a distributed Dijkstra visitor. The suble differences
between sequential and distributed Dijkstra visitors are discussed in the
section Visitor Event Points.
UTIL/OUT: color_map(ColorMapcolor)
The color map must be a Distributed Property Map with the same
process group as the graph g whose colors must monotonically
darken (white -> gray -> black). The default value is a distributed
iterator_property_map created from a std::vector of
default_color_type.
В:lookahead (distance_typelook)
При подаче этого параметра реализация будет использовать алгоритмEager Dijkstraс заданным значением lookahead. Lookahead позволяет распределённому алгоритму Дейкстры спекулятивно обрабатывать вершины, кратчайшее расстояние от источника которых, возможно, ещё не было найдено. Когда найденное расстояние является самым коротким расстоянием, параллелизм улучшается, и алгоритм может закончиться быстрее. Однако, если расстояние не является самым коротким расстоянием, вершину нужно будет переработать позже, что приведет к большей работе.
Типрасстояние_типявляется типом значенияДистанционная картакарта свойств. Это неотрицательное значение, определяющее, насколько далеко алгоритм Дейкстры может обрабатывать значения.
КонцепцияDijkstra Visitorопределяет 7 точек событий, которые будут вызваны последовательной реализациейDijkstra. Распределенная Дейкстра сохраняет эти точки событий, но последовательность событий и процесс, в котором происходит каждое событие, будут меняться в зависимости от распределения графа, смотрящего и краевого веса.
initialize_vertex(s,g)
This will be invoked by every process for each local vertex.
discover_vertex(u,g)
This will be invoked each type a process discovers a new vertex
u. Due to incomplete information in distributed property maps,
this event may be triggered many times for the same vertex u.
examine_vertex(u,g)
This will be invoked by the process owning the vertex u. This
event may be invoked multiple times for the same vertex when the
graph contains negative edges or lookahead is employed.
examine_edge(e,g)
This will be invoked by the process owning the source vertex of
e. As with examine_vertex, this event may be invoked
multiple times for the same edge.
edge_relaxed(e,g)
Similar to examine_edge, this will be invoked by the process
owning the source vertex and may be invoked multiple times (even
without lookahead or negative edges).
edge_not_relaxed(e,g)
Similar to edge_relaxed. Some edge_not_relaxed events that
would be triggered by sequential Dijkstra's will become
edge_relaxed events in distributed Dijkstra's algorithm.
finish_vertex(e,g)
See documentation for examine_vertex. Note that a "finished"
vertex is not necessarily finished if lookahead is permitted or
negative edges exist in the graph.
Формулировка алгоритма Дейкстры Краузером, Мелхорном, Мейером и Сандерсом[CMMS98a]улучшает масштабируемость параллельного алгоритма Дейкстры, увеличивая количество вершин, которые могут быть обработаны на данном супершаге. Этот алгоритм хорошо адаптируется к различным типам графов и представляет собой простой алгоритм для использования, не требующий дополнительного ввода пользователя для достижения разумной производительности. Недостатком этого алгоритма является то, что реализация требуется для управления тремя приоритетными очередями, что создает большой объем работы на каждом узле.
Этот алгоритм используется по умолчанию в распределенныхdijkstra_shortest_paths().
Этот алгоритм выполняетO(V log V)работу вd + 1супершагов BSP, гдеdв лучшем случаеO(V), но, как правило, намного меньше. На направленных графах Эрдоса-Реньи с краевыми весами в [0, 1] ожидаемое число супершаговdсоставляетO(n^(1/3)]с высокой вероятностью.
Следующие диаграммы иллюстрируют производительность параллельной реализации BGL алгоритма Crauser et al. на графиках с краевыми весами, равномерно выбранными из диапазона. [0, 1].
На каждом супершаге параллельный алгоритм Дейкстра обычно обрабатывает только узлы, расстояния которых эквивалентны глобальному минимальному расстоянию, поскольку эти расстояния гарантированно верны. Эта вариация алгоритма позволяет алгоритму обрабатывать все вершины, расстояния которых находятся в пределах некоторого постоянного значения минимального расстояния. Значение называется значением и предоставляется пользователем в качестве пятого параметра функции. Небольшие значения параметра lookahead, скорее всего, приведут к ограниченным возможностям параллелизации, тогда как большие значения обнаружат больше параллелизма, но могут ввести (небесное) зацикливание и привести к дополнительной работе. Оптимальное значение параметра lookahead зависит от входного графика; см.[CMMS98b]и[MS98].
Этот алгоритм будет использоватьсяdijkstra_shortest_paths(), когда ему будет присвоено значение lookahead.
Этот алгоритм выполняетO(V log V)работу вd + 1BSP-супершагах, гдеdявляется максимумомO(V), но может быть меньше в зависимости от величины наклона. Алгоритм может выполнять больше работы, когда обеспечивается большой внешний вид, потому что вершины будут переработаны.
Производительность алгоритма нетерпеливой Дейкстры сильно варьируется в зависимости от значения смотрящего. Следующие диаграммы иллюстрируют производительность параллельного BGL на графиках с краевыми весами, равномерно выбранными из диапазона[0, 1]и постоянным внешним видом 0,1.
Алгоритм дельта-шага[MS98]является еще одним вариантом параллельного алгоритма Дейкстра. Как и нетерпеливый алгоритм Dijkstra, он использует значение lookaheaddelta, которое позволяет процессорам обрабатывать вершины, прежде чем мы гарантированно найдем их минимальные расстояния, что позволяет больше параллелизма, чем консервативная стратегия. Delta-stepping также вводит многоуровневую структуру данных ковша, которая обеспечивает более расслабленные ограничения упорядочивания, чем приоритетные очереди, используемые другими вариантами Dijkstra, уменьшая сложность вставок, релаксации и удаления из центральной структуры данных. Алгоритм дельта-шага является наиболее эффективным из вариантов Dijkstra.
Значение lookaheadдельтаопределяет, насколько большим будет каждое из "buckets" в пределах дельта-ступенчатой очереди, где оно содержит края в пределах предварительных расстояний междудельта''i''delta''*(i+1).''дельтадолжна иметь положительное значение. При опущениидельтаустанавливается на максимальный вес края, деленный на максимальную степень.
