Алгоритм беллмана форда и дейкстры отличия

Обновлено: 05.02.2025

Его принцип заключается в выполнении не более V-1 операций релаксации на графе, чтобы получить все возможные кратчайшие пути. Его преимущество перед алгоритмом Дейкстры состоит в том, что вес ребра может быть отрицательным, а реализация проста.Недостатком является слишком высокая временная сложность, вплоть до O (VE). Но алгоритм можно оптимизировать несколькими способами, что повышает эффективность.

Алгоритм Беллмана-Форда каждый раз расслабляет все ребра, и каждый раз, когда он расслабляется, он получает кратчайший путь, поэтому общее количество требуемых операций релаксации составляет V-1 раз. Если расслабление все еще может быть достигнуто после стольких расслаблений, это означает, что оно содержит отрицательное кольцо.

по сравнению сАлгоритм ДейкстрыСамым большим преимуществом является то, что Bellman-Ford поддерживает отрицательные веса, а реализация кода относительно проста. Недостатком является то, что временная сложность высока, достигая O (V * E), V представляет количество вершин, а E представляет количество ребер.

Может использоваться для решения следующих задач:

Есть ли путь к каждому узлу из A (вы, конечно, можете добраться до него, если у вас есть вычисленное значение);
Кратчайший путь от A до каждого узла (наименьшее время или наименьший путь и т. Д.)
Есть ли на графике отрицательная петля (сумма весов отрицательная)

Во время инициализации расстояние dist (s-> v) от начальной точки s до каждой вершины v присваивается ∞, а dist (s-> s) присваивается 0

Следуйте за n-1 операциями обхода (n - количество вершин, метод ввода с верхним индексом v не может быть введен . ) и выполняйте операции релаксации на всех ребрах, предполагая:

Так называемое расслабление, возьмите сторону ab в качестве примера, если dist (a) представляет собой общую стоимость начальной точки s для достижения точки a, dist (b) представляет собой стоимость начальной точки s для достижения точки b. Общее количество, weight (ab) представляет собой вес ребра ab, , если он существует:

Это означает, что существует более короткий путь к b, s -> . -> a-> b, общая стоимость обновления точки b составляет (dist (a) + weight (ab)), а родительский узел - это

Если после завершения обхода вы выполните еще один обход, и вы можете получить более короткий путь от s до некоторых узлов, это означает, что существует отрицательный цикл

случай

Дело номер один

Для начала приведите общий пример в Интернете, чтобы представить идею его реализации:

Как показано на рисунке ниже, получить кратчайший путь от начальной точки A до конечной точки в соответствии с идеей алгоритма Беллмана-Форда.

Как видно из приведенного выше введения, поскольку общее количество вершин в графе n = 5 вершин, требуются 5-1 = 4 операции обновления обхода. Если для каждой операции может быть найден более короткий путь, значение соответствующего узла обновляется

1. Сначала установите информацию о граничном объекте, начиная с исходной точки A, в порядке от ближнего к дальнему, иначе dist (s) == ∞ усложнит последующие вычисления:

1. Сначала укажите время от начальной точки A до каждого узла:

Родительский узел	узел	инициализация
A	A	0
..	B	∞
..	C	∞
..	D	∞
..	E	∞

2. Выполните первую операцию релаксации на всех краях:

2.1 Подсчитайте значения AB, AC узлов, которые могут быть достигнуты через 1 ребро:

Родительский узел	узел	Стоимость
A	A	0
A	B	-1
A	C	4
..	D	∞
..	E	∞

2.2 Подсчитайте значения BC, BD, BE узлов, которые могут быть достигнуты через 2 ребра:

Родительский узел	узел	Стоимость
A	A	0
A	B	-1
B	C	2
B	D	1
B	E	1

Возьмите узел C в качестве примера, потому что он удовлетворяет: dist (B) + weight (BC)> dist (C), то есть -1 + 3> 4, поэтому C обновляется до 2

2.3 Подсчитайте значения ED, DC узлов, которые могут быть достигнуты через 3 ребра:

Родительский узел	узел	Стоимость
A	A	0
A	B	-1
B	C	2
E	D	-2
B	E	1

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

Родительский узел	узел	Стоимость
A	A	0
A	B	-1
B	C	2
E	D	-2
B	E	1

4. Из приведенной выше таблицы видно, что в это время получены кратчайший путь и маршрут от исходной точки A до каждого узла.

Случай второй

Как показано на рисунке ниже, найдите кратчайший путь от A до каждого узла.

1. Граф имеет всего 7 узлов, и требуется не более 7-1 = 6 релаксационных операций на всех ребрах.

2. Сначала создайте объект края:

3. Выполните первую операцию релаксации обхода, вы можете получить:

Родительский узел	узел	Стоимость
A	A	0
C	B	3
D	C	3
A	D	5
B	E	2
D	F	4
E	G	5

4. Выполните вторую операцию релаксации обхода, чтобы получить:

Родительский узел	узел	Стоимость
A	A	0
C	B	1
D	C	3
A	D	5
B	E	0
D	F	4
E	G	3

5. Выполните третью операцию резерва обхода, результат больше не обновляется:

Родительский узел	узел	Стоимость
A	A	0
C	B	1
D	C	3
A	D	5
B	E	0
D	F	4
E	G	3

6. В это время кратчайший путь от A до каждого узла на верхнем краю таблицы может быть получен в обратном порядке.

8. Здесь предполагается, что граничные объекты одного и того же уровня (начиная с A, могут быть достигнуты через одинаковое количество ребер, например, DC, CB, BE, DF, CE могут быть достигнуты через 2 ребра) позиция сортировки регулируется, и Не повлияет на правильность результатов, но повлияет на количество требуемых обходов (разные уровни):

Например, выше, AB: 6, AC: 5, AD: 5, CB: -2, DC: -2, BE: -1, CE: 1, DF: -1, EG: 3, FG: 3, необходимо пройти код 3. Результат можно подтвердить только один раз (последний раз, использованный для подтверждения результата, не будет обновлен);

AB: 6, AC: 5, AD: 5, DC: -2, CB: -2, BE: -1, CE: 1, DF: -1, EG: 3, FG: 3 код необходимо пройти дважды проверить результаты;

AB: 6, AC: 5, AD: 5, BE: -1, CE: 1, DF: -1, DC: -2, CB: -2, EG: 3, FG: 3 Код необходимо пройти 4 раза. проверить результаты;

Иногда взаимосвязь графика вводится пользователем, и порядок плохой, и он должен быть лучшим, чтобы заставить

ограничение

Случай третий, есть отрицательный цикл

Измените график случая 1 B-> D на -2. Сделайте B D образующим отрицательный цикл. Так называемый отрицательный цикл относится к отрицательной сумме весов цикла, такой как на рисунке 1 + ( -2) = -1

Поскольку отрицательный цикл может выполнять шаги цикла бесконечно, столько, сколько вы хотите, вы можете бесконечно повторять цикл на B-> D-> B-> D . поэтому значение B и D может быть бесконечно малым, Затем, когда значения B и D бесконечно малы, а затем отходят от узлов B и D, чтобы достичь других узлов, значения других узлов также будут близки к бесконечно малым. Следовательно, для случая отрицательных петель, Bellman-Ford Можно только судить о том, что у графа есть отрицательный цикл, но кратчайший путь к каждому узлу не найден.

После того, как Беллман-Форд находит кратчайший путь к каждому узлу, его можно пройти снова, чтобы определить, существует ли отрицательный цикл.

Например, в том же случае 1 результат получается после выполнения 4 обходов по графику:

Родительский узел	узел	Стоимость	Линия исполнения
A	A	0
A	B	-2	A->B->D->B
B	C	1	A->B->D->B->C
E	D	-4	A->B->D-B->D
B	E	0	A->B->D->B->E

По истечении этого времени полученный результат не является правильным кратчайшим путем. Например, выполните другой обход, чтобы обновить значение узла, который может быть достигнут через 5 ребер из исходной точки A.

Родительский узел	узел	Стоимость	Линия исполнения
A	A	0
A	B	-3	A->B->D->B->D->B
B	C	1	A->B->D->B->C
E	D	-4	A->B->D-B->D
B	E	0	A->B->D->B->E

Обнаружение того, что существует узел B, который может быть обновлен в это время, доказывает наличие отрицательного цикла на графике.

Если количество раз не ограничено, кратчайший путь для каждого узла не может быть получен. Если количество обходов искусственно ограничено, может быть найден кратчайший путь от исходной точки до каждого узла.

резюме

1. Алгоритм в ширину BFS в основном подходит для поиска пути с наименьшим количеством шагов от исходной точки до конечной точки без веса графа. Когда диаграмма направлений имеет вес, он больше не применим

2. Алгоритм Дейкстры Дейкстра в основном используется для поиска кратчайшего пути во взвешенном направленном графе, но он не подходит для ситуации с отрицательным весом. Для кольцевого графа мое личное ощущение такое же, как и в BFS, отмечая обработанные узлы, чтобы избежать В бесконечный цикл может поддерживать

3. Алгоритм Беллмана-Форда Беллмана-Форда в основном используется в направленных графах с отрицательными весами (он также может использоваться без отрицательных весов, но эффективность намного ниже, чем у Дейкстры) для поиска кратчайшего пути от исходной точки до каждого узла.

4. Беллман-Форд может определить, есть ли на графике отрицательный цикл, но не поддерживает вычисление кратчайшего пути каждого узла, когда есть отрицательный цикл. Требуется выполнить еще один обход только после завершения обхода (количество узлов - 1). Если данные могут быть обновлены, это означает, что существует отрицательный цикл.

5. Когда количество обходов искусственно ограничено, отрицательный цикл также может быть вычислен, но, похоже, не имеет практического значения.

Наверняка многим из гейм-девелоперов (или просто людям, увлекающимися програмировагнием) будет интересно услышать эти четыре важнейших алгоритма, решающих задачи о кратчайших путях.

Сформулируем определения и задачу.
Графом будем называть несколько точек (вершин), некоторые пары которых соединены отрезками (рёбрами). Граф связный, если от каждой вершины можно дойти до любой другой по этим отрезкам. Циклом назовём какой-то путь по рёбрам графа, начинающегося и заканчивающегося в одной и той же вершине. И ещё граф называется взвешенным, если каждому ребру соответствует какое-то число (вес). Не может быть двух рёбер, соединяющих одни и те же вершины.
Каждый из алгоритмов будет решать какую-то задачу о кратчайших путях на взвешенном связном. Кратчайший путь из одной вершины в другую — это такой путь по рёбрам, что сумма весов рёбер, по которым мы прошли будет минимальна.
Для ясности приведу пример такой задачи в реальной жизни. Пусть, в стране есть несколько городов и дорог, соединяющих эти города. При этом у каждой дороги есть длина. Вы хотите попасть из одного города в другой, проехав как можно меньший путь.

Считаем, что в графе n вершин и m рёбер.
Пойдём от простого к сложному.

Алгоритм Флойда-Уоршелла

Алгоритм Форда-Беллмана

Алгоритм Дейкстры

Алгоритм Дейкстры для разреженных графов

Делает то же самое, что и алгоритм Дейкстры, но за количество операций порядка m * log(n). Следует заметить, что m может быть порядка n^2, то есть эта вариация алгоритма Дейкстры не всегда быстрее классической, а только при маленьких m.
Что нам нужно в алгоритме Дейкстры? Нам нужно уметь находить по значению d минимальную вершину и уметь обновлять значение d в какой-то вершине. В классической реализации мы пользуемся простым массивом, находить минимальную по d вершину мы можем за порядка n операций, а обновлять — за 1 операцию. Воспользуемся двоичной кучей (во многих объектно-ориентированных языках она встроена). Куча поддерживает операции: добавить в кучу элемент (за порядка log(n) операций), найти минимальный элемент (за 1 операцию), удалить минимальный элемент (за порядка log(n) операций), где n — количество элементов в куче.
Создадим массив d[0… n — 1] (его значение то же самое, что и раньше) и кучу q. В куче будем хранить пары из номера вершины v и d[v] (сравниваться пары должны по d[v]). Также в куче могут быть фиктивные элементы. Так происходит, потому что значение d[v] обновляется, но мы не можем изменить его в куче. Поэтому в куче могут быть несколько элементов с одинаковым номером вершины, но с разным значением d (но всего вершин в куче будет не более m, я гарантирую это). Когда мы берём минимальное значение в куче, надо проверить, является ли этот элемент фиктивным. Для этого достаточно сравнить значение d в куче и реальное его значение. А ещё для записи графа вместо двоичного массива используем массив списков.
m раз добавляем элемент в кучу, получаем порядка m * log(n) операций.
Псевдокод:

Задача: Дан граф и начальная вершина src в графе, необходимо найти кратчайшие пути от src до всех вершин в данном графе. В графе могут присутствовать ребра с отрицательными весами.

Мы уже обсуждали алгоритм Дейкстры в качестве способа решения этой задачи. Алгоритм Дейкстры является жадным алгоритмом, а его сложность равна O(VLogV) (с использованием кучи Фибоначчи). Однако Дейкстра не работает для графов с отрицательными весами ребер, тогда как Беллман-Форд — вполне. Алгоритм Беллмана-Форда даже проще, чем алгоритм Дейкстры, и хорошо подходит для распределенных систем. В то же время сложность его равна O(VE), что больше, чем показатель для алгоритма Дейкстры.

Рекомендация: Прежде, чем двигаться к просмотру решения, попробуйте попрактиковаться самостоятельно.

Алгоритм

Ниже приведены подробно расписанные шаги.

На этом шаге инициализируются расстояния от исходной вершины до всех остальных вершин, как бесконечные, а расстояние до самого src принимается равным 0. Создается массив dist[] размера |V| со всеми значениями равными бесконечности, за исключением элемента dist[src] , где src — исходная вершина.
Вторым шагом вычисляются самые короткие расстояния. Следующие шаги нужно выполнять |V| -1 раз, где |V| — число вершин в данном графе.
- Произведите следующее действие для каждого ребра u-v:
  Если dist[v] > dist[u] + вес ребра uv , то обновите dist[v]
  dist [v] = dist [u] + вес ребра uv
На этом шаге сообщается, присутствует ли в графе цикл отрицательного веса. Для каждого ребра u-v необходимо выполнить следующее:

Если dist[v] > dist[u] + вес ребра uv , то в графе присутствует цикл отрицательного веса.

Как это работает? Как и в других задачах динамического программирования, алгоритм вычисляет кратчайшие пути снизу вверх. Сначала он вычисляет самые короткие расстояния, то есть пути длиной не более, чем в одно ребро. Затем он вычисляет кратчайшие пути длиной не более двух ребер и так далее. После i-й итерации внешнего цикла вычисляются кратчайшие пути длиной не более i ребер. В любом простом пути может быть максимум |V|-1 ребер, поэтому внешний цикл выполняется именно |V|-1 раз. Идея заключается в том, что если мы вычислили кратчайший путь с не более чем i ребрами, то итерация по всем ребрам гарантирует получение кратчайшего пути с не более чем i + 1 ребрами (доказательство довольно простое, вы можете сослаться на эту лекцию или видеолекцию от MIT)

Пример

Давайте разберемся в алгоритме на следующем примере графа. Изображения взяты отсюда.
Пусть начальная вершина равна 0. Примите все расстояния за бесконечные, кроме расстояния до самой src . Общее число вершин в графе равно 5, поэтому все ребра нужно пройти 4 раза.

Пусть ребра отрабатываются в следующем порядке: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D). Мы получаем следующие расстояния, когда проход по ребрам был совершен первый раз. Первая строка показывает начальные расстояния, вторая строка показывает расстояния, когда ребра (B, E), (D, B), (B, D) и (A, B) обрабатываются. Третья строка показывает расстояние при обработке (A, C). Четвертая строка показывает, что происходит, когда обрабатываются (D, C), (B, C) и (E, D).

Первая итерация гарантирует, что все самые короткие пути будут не длиннее пути в 1 ребро. Мы получаем следующие расстояния, когда будет совершен второй проход по всем ребрам (в последней строке показаны конечные значения).

Вторая итерация гарантирует, что все кратчайшие пути будут иметь длину не более 2 ребер. Алгоритм проходит по всем ребрам еще 2 раза. Расстояния минимизируются после второй итерации, поэтому третья и четвертая итерации не обновляют значения расстояний.

Выходные значения:

Аннотация научной статьи по математике, автор научной работы — Барыбин Д.А., Кофман Е.Ю., Шульгин М.С.

Рассмотрены основные этапы проектирования топологии сети и возможные проблемы, возникающие при ее построении. Произведен сравнительный анализ трудоемкости алгоритмов Дейкстры и БеллманаФорда, реализуемых при решении задачи о нахождении кратчайшего пути в протоколах маршрутизации. Разработаны программные коды на языке С++ для конкретной топологии сети .

Похожие темы научных работ по математике , автор научной работы — Барыбин Д.А., Кофман Е.Ю., Шульгин М.С.

Метод обеспечения устойчивости телекоммуникационной сети за счет использования ее топологической избыточности

Орёл, Россия Кофман Е.Ю. к.ф-м.н, сотрудник

Орёл, Россия Шульгин М.С. сотрудник

СРАВНЕНИЕ АЛГОРИТМОВ ДЕЙКСТРЫ И БЕЛЛМАНА-ФОРДА ПРИ РЕШЕНИИ ЗАДАЧИ О ПОИСКЕ КРАТЧАЙШЕГО ПУТИ В ПРОТОКОЛАХ МАРШРУТИЗАЦИИ

Рассмотрены основные этапы проектирования топологии сети и возможные проблемы, возникающие при ее построении. Произведен сравнительный анализ трудоемкости алгоритмов Дейкстры и Беллмана-Форда, реализуемых при решении задачи о нахождении кратчайшего пути в протоколах маршрутизации. Разработаны программные коды на языке С++ для конкретной топологии сети.

Алгоритм Дейкстры, алгоритм Беллмана-Форда, топология сети, кратчайший путь.

В области сетевых технологий задача поиска кратчайшего пути наиболее остро стоит при построении топологии сети с использованием протоколов маршрутизации. От правильно спланированной и построенной топологии сети зависит работоспособность и состояние системы. В настоящее время чаще всего используются протоколы, в основе работы которых лежит алгоритм Дейкстры или Беллмана-Форда.

При проектирования топологии сети, как правило, выделяют 4 основных этапа:

1. Определение свободных ресурсов.

2. Выбор и реализация протоколов маршрутизации.

3. Проверка выполнения необходимых условий.

4. Утверждение маршрута.

Наиболее трудоемкими являются реализация протоколов маршрутизации и проверка выполнения всех необходимых условий.

При построении сети существует множество различных наборов соглашений, которые можно выбрать для решения задачи о поиске кратчайшего пути. Однако в случаях с территориально большой сетью необходимо применять несколько протоколов для быстрой и корректной работы маршрутизаторов, при этом количество возможных протоколов сужается. В большинстве случаев выбор падает на ISIS, OSPF или RIP, в которых реализуются алгоритмы Дейкстры и Беллмана-Форда соответсвенно.

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

Рассмотрим алгоритмы Дейкстры и Беллмана-Форда нахождения кратчайшего пути и их воздействие на центральный процессор во время работы. Расчет кратчайшего маршрута реализуем посредством ЭВМ.

Сеть связи обычно рассматривается как графовые модели, где коммутаторами или маршрутизаторами являются узлы, а множествои линий связи являются дугами. Пример подобного графа из 15 узлов представлен на рисунке 1.

Алгоритм Дейкстры был разработатн голландским ученым в 1959 году. Основная цель алгоритма -нахождение кратчайшего расстояния от одной вершины графа до всех остальных. В настоящее время данный метод является достаточно востребованным, однако он реализуем только с ребрами имеющими положительный вес. Вычислительная сложность алгоритма рассчитывается по формуле: 0(п2 + т). Алгоритм Дейкстры существует в нескольких вариантах. В одном из них он пошагово просматривает все возможные пути от начальной вершины к конечной, пока не будет найден наименьший. В других случаях принцип работы заключается в том, что фиксируется один узел как исходный и ищутся кратчайшие пути от него до всех остальных вершин графа. Данный алгоритм используется при создании сетевых протоколов маршрутизации. Одним из таких протоколов является IS-IS. Алгоритм Дейкстры также лежит в основе протокола OSPF.

Другой вариант решения задачи о поиске кратчайшего пути был предложен двумя американскими математиками Ричардом Беллманом и Лестором Фордом. Разработанный алгоритм был предназначен для поиска пути во взвешенных графах, ребра которых могут иметь отрицательный вес. Также в результате поиска кратчайшего пути оказывается возможным попасть в одну и туже вершину графа несколько раз. Формула для расчета вычислительной сложности имеет вид: 0(n*m). Этот алгоритм используется в некоторых протоколах дистанционно-векторной маршрутизации, например в RIP (Routing Information Protocol - Протокол маршрутной информации).

Программный код, реализующий алгоритм Беллмана-Форда на языке С++ и демонстрирующий переход по вершинам графа, представленного на рисунке 1, представлен ниже.

void QVertex::hoverMoveEvent(QGraphicsSceneHoverEvent *event)

Рисунок 1 - Топология сети

highlightAllNeighbours(255,0,0,255); QGraphicsItem:: hoverMoveEvent(event);

void QVertex::hoverLeaveEvent(QGraphicsSceneHoverEvent *event)

lightsoffAllNeighbours(); QGraphicsItem:: hoverLeaveEvent(event);

void QVertex::highlight(int r, int g, int b, int alpha)

QColor color(r,g,b,alpha); QPen pen(color); pen.setStyle(Qt::SolidLine); QGraphicsEllipseItem::setPen(pen); label->setDefaultTextColor(color);

void QVertex::highlightAllNeighbours(int r, int g, int b, int alpha)

QColor color(r,g,b,alpha); QPen pen(color); pen.setStyle(Qt:: SolidLine); QGraphicsEllipseltem: :setPen(pen); label->setDefaultTextColor(color); setZValue( 10); for(int a=0; a < graph->intE(); a++)< if (lineE)

lineE [a] ->highlight(r,g,b,alpha); else

highlightAllNeighbours(0,0,0,255); for(int a=0; a < graph->intE(); a++)< if (lineE)

if(lineE[a] ->WP() == id || lineE[a]->WK() == id)

lineE [a] ->lightsoff(); > >

if(lineE[a] ->WP() == id || lineE[a]->WK() == id) lineE[a]->lightsoffDejkstra(); >

int QVertex::minV(QVertex **tab, int size)

QEdge * QVertex::incidentEdge(int Vx)

return lineE[i]; > else if(lineE[i]->WK() == id)< if(lineE[i]->WP() == Vx)

Рассмотрим конкретную задачу поиска кратчайшего маршрута, например из точки 7 в точку 5 для сети, представленной в виде графа из 15 узлов (рисунок 1). Проанализируем затраченное время и ресурсы (нагрузки на ЦП) при реализации обоих алгоритмов.

При запуске алгоритма Дейкстры ЦП нагрузился на 17%, о чем информирует график нагрузки на ЦП. Время, затраченное на нахождение кратчайшего пути от точки 7 до точки 5 равно 30 секунд. На рисунке 2 показано, как при запуске программы возрастает нагрузка на центральный процессор.

Рисунок 2 - Нагрузка на ЦП при использовании алгоритма Дейкстры

При решении тойже задачи с использованием алгоритма Беллмана-Форда видим, что резкий скачок нагруженности ЦП состваил всего 10%, при этом затрачено всего 12 секунд (рисунок 3).

Рисунок 3. Нагрузка на ЦП при использовании алгоритма Беллмана-Форда

Анализируя решение задачи о поиске кратчайшего пути на графе из 15 узлов, можно отметить, что алгоритм Беллмана-Форда эффективнее и дает результирующий ответ быстрее, затрачивая при этом наименьшие ресурсы. Однако, для развивающихся сетей, с динамическим изменением маршрутов и числом переходов большим 15 (без отрицательных весов) рекомендуется использовать более сложные протоколы ISIS или OSPF, работающие на алгоритме Дейкстры. В случае малых сетей с количеством переходов не более 15, где возможна отрицательная метрика, допускается использование протокола RIP, который реализует алгоритм Беллмана-Форда.

Список использованной литературы:

1. Берж К. Теория алгоритмов и её применение / К. Бержю - Москва: Мир, 1980.

2. Зыков А.А. Теория конечных графов / А.А. Зыков - Новосибирск: Наука, 1969.

3. Изотова Т.Ю. Обзор алгоритмов поиска кратчайшего пути в графе / Т.Ю. Изотова // Новые информационные технологии в автоматизированных системах: материалы девятнадцатого научно-практического семинара. - М.: ИПМ им. М.В. Келдыша, 2016. С. 341-344.

4. Кормен Т.Х. Алгоритмы: построение и анализ / Т.Х. Кормен, Ч.И. Лейзерсон, Р.Л. Ривест, К. Штайн -Москва: Вильямс, 2006.

УДК 351.862.2, 630.841.21

старший научный сотрудник ФГБУ ВНИИ ГОЧС (ФЦ)

научный сотрудник ФГБУ ВНИИ ГОЧС (ФЦ)

АНАЛИЗ ЭФФЕКТИВНОСТИ ПРОВОДИМЫХ МЕРОПРИЯТИЙ ПО ЗАЩИТЕ НАСЕЛЕНИЯ И ТЕРРИТОРИИ ОТ ОПАСНЫХ ПРИРОДНЫХ ЯВЛЕНИЙ В РЕСПУБЛИКЕ ЯКУТИЯ В 2020 ГОДУ

Проведен анализ эффективности мероприятий по защите населения и территории от опасных природных явлений в Республике Якутия в 2020 году с выработкой предложений по снижению ущерба.

опасные природных явлений, подтопление, пункты длительного пребывания.

Опасные природные явления неизбежно будут оказывать влияние на повседневную жизнь населения и экономические показатели Республики Якутия.

В целях организации выполнения на территории республики комплекса подготовительных мероприятий для предупреждения крупномасштабных ЧС в период пропуска весеннего половодья и летне-

Читайте также: