Каково худшее время работы алгоритма беллмана форда на графе с n вершинами
Обновлено: 14.05.2024
Алгоритм Беллмана–Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| ? |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана–Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом.
Также как и алгоритм Дейкстры, алгоритм Беллмана — Форда вычисляет во взвешенном графе кратчайшие пути от одной вершины до всех остальных. Он подходит для работы с графами, имеющими ребра с отрицательным весом. Но спектр применимости алгоритма затрагивает не все такие графы, ввиду того, что каждый очередной проход по пути, составленному из ребер, сумма весов которых отрицательна (т. е. по отрицательному циклу), лишь улучшает требуемое значение. Бесконечное число улучшений делает невозможным определение одного конкретного значения, являющегося оптимальным. В связи с этим алгоритм Беллмана — Форда не применим к графам, имеющим отрицательные циклы, но он позволяет определить наличие таковых.
Решить задачу, т. е. найти все кратчайшие пути из вершины s до всех остальных, используя алгоритм Беллмана — Форда, это значит воспользоваться методом динамического программирования: разбить ее на типовые подзадачи, найти решение последним, покончив тем самым с основной задачей. Здесь решением каждой из таких подзадач является определение наилучшего пути от одного отдельно взятого ребра, до какого-либо другого. Для хранения результатов работы алгоритма заведем одномерный массив d[]. В каждом его i-ом элементе будет храниться значение кратчайшего пути из вершины s до вершины i (если таковое имеется). Изначально, присвоим элементам массива d[] значения равные условной бесконечности (например, число заведомо большее суммы всех весов), а в элемент d[s] запишем нуль. Так мы задействовали известную и необходимую информацию, а именно известно, что наилучший путь из вершины s в нее же саму равен 0, и необходимо предположить недоступность других вершин из s. По мере выполнения алгоритма, для некоторых из них, это условие окажется ложным, и вычисляться оптимальные стоимости путей до этих вершин из s(по материалам kvodo).
Целью курсового проекта является исследование процессов маршрутизации. В курсовом пректе будут рассмотрены алгоритмы поиска кратчайшего пути, произведён расчёт пути с минимальным количеством переходов. Также рассмотрим характеристики протокола RIP и построим маршрутные таблицы.
Краткий обзор постановки задачи и путей ее решения
Компьютерные сети, как правило, представляются в виде графов, при этом коммутаторы и маршрутизаторы сетей являются узлами графа, а линии связи представляют собой р алгоритм Беллмана- Форда), ребра графа. Ряд понятий из теории графов оказываются полезными при разработке сетей и алгоритмов маршрутизации. Для объединенной сети, такой как Интернет или интранет, представление ее в виде ориентированного графа также является приемлемым. В этом случае каждой вершине соответствует маршрутизатор. Если два маршрутизатора напрямую соединены к одной и той же локальной или глобальной сети, тогда это двусторонне соединение соответствует паре параллельных ребер, соединяющих соответствующие вершины. Если к сети напрямую присоединены более двух маршрутизаторов, тогда эта сеть представляется в виде множества пар параллельных ребер, каждая из которых соединяет два маршрутизатора. В объединенной сети для передачи IP-дейтаграммы от маршрутизатора - источника к маршрутизатору - приемнику по разным линиям через разные сети и маршрутизаторы пакетов требуется принять решение о выборе маршрута. Эта задача также эквивалентна поиску пути в графе.
Сеть с коммутацией пакетов (или сеть ретрансляции кадров, или сеть ATM) но рассматривать как ориентированный граф, в котором каждая вершина соответствует узлу коммутации пакетов, а линии связи между узлами соответствует пара параллельных ребер, по каждому из которых данные передаются в одном направлении. В такой сети для передачи пакета от узла-источника узлу - получателя по разным линиям через несколько коммутаторов пакетов требуется принять решение о выборе маршрута. Эта задача эквивалентна поиску пути в графе.
Практически во всех сетях с коммутацией пакетов и во всех объединенных сетях решение о выборе маршрута принимается на основе одной из разновидностей критерия минимальной стоимости. Если выбирается маршрут с минимальным количеством ретрансляционных участков (хопов), тогда каждому ребру, соответствующему ретрансляционному участку, назначается единичный вес. Эта задача соответствует поиску кратчайшего пути в обычном (не взвешенном) графе. Но чаще всего каждому ретрансляционному участку в соответствие ставится определенная величина, называемая стоимостью (cost) передачи. Эта величина может быть обратно пропорциональной пропускной способности линии, прямо пропорциональной текущей нагрузке на эту линию или представлять собой некую комбинацию подобных параметров. При расчете стоимости могут учитываться также такие критерии, как финансовая стоимость использования ретрансляционного участка. В любом случае, стоимости использования ретрансляционных участков являются входными данными для алгоритма поиска пути с минимальной стоимостью, который может быть сформулирован следующим образом.
Пусть имеется сеть, состоящая из узлов, соединенных двунаправленными линиями связи, и каждой линии поставлена в соответствие стоимость пересылки данных в каждом направлении. Стоимость пути между двумя узлами определяете как сумма стоимостей всех линий, входящих в данный путь. Задача состоит в том, чтобы найти путь с наименьшей стоимостью для каждой пары узлов.
Обратите внимание на то, что стоимость использования ретрансляционного участка может быть разной в разных направлениях. Например, это справедливо в случае, если стоимость использования ретрансляционного участка пропорциональна длине очереди дейтаграмм, ждущих передачи. В теории графов задаче нахождения пути с наименьшей стоимостью соответствует задача поиска пути с наименьшей длиной во взвешенном ориентированном графе.
Большинство алгоритмов поиска маршрута с наименьшей стоимостью, применяющихся в сетях с коммутацией пакетов и объединенных сетях, представляют собой вариации одного из двух общих алгоритмов, известных как алгоритм Дейкстры (Dijkstra) и алгоритм Беллмана — Форда (Bellman — Ford). В этом разделе обсуждаются оба алгоритма.
Исходные данные
V1 V2 V3 V4 V5 V6
Рисунок 1. Взвешенный ориентированный граф, построенный по матрице смежности
V1 V3
Алгоритм Дейкстры
Алгоритм Дейкстры может быть сформулирован следующим образом. Алгоритм находит кратчайшие пути от данной вершины-источника до всех остальных вершин, перебирая пути в порядке увеличения их длин. Работа алгоритма проходит поэтапно. К k-му шагу алгоритм находит kкратчайших (с наименьшей стоимостью) путей к k вершинам, ближайшим к вершине-источнику. Эти вершины образуют множество Т.На шаге (k + 1) к множеству Тдобавляется вершина, ближайшая к вершине- источнику среди вершин, не входящих во множество Т.При добавлении каждой новой вершины к множеству Т определяется путь к ней от источника. Формально этот алгоритм может быть определен следующим образом. Введем обозначения:
· N — множество вершин сети;
· s— вершина-источник;
· Т— множество вершин, уже обработанных алгоритмом;
· Дерево— связующее дерево для вершин, принадлежащих множеству Т,включая ребра, входящие в пути с наименьшей стоимостью от вершины s до каждой вершины множества Т;
· w(i,j) — стоимость линии от вершины iдо вершины j, причем w(i, j) = 0или w(i,j) = ¥, если две вершины не соединены напрямую, и w(i, j) =>0, если две вершины соединены напрямую;
· L(n) — минимальная стоимость пути от вершины s до вершины п, известного на данный момент алгоритму (по завершении работы алгоритма это минимальная стоимость пути от вершины s до вершины п).
Алгоритм состоит из трех шагов. Шаги 2 и 3 повторяются до тех пор, пока множество T не совпадет с множеством N. Это значит, что шаги 2 и 3 повторяются, пока для всех вершин сети не будут найдены окончательные пути.
1. Инициализация. Т=Дерево = ,
то есть множество исследованных вершин состоит пока что только из вершины-источника.
L(n) = w(s, п) для п ¹ s,
то есть стоимости начальных путей к соседним вершинам представляют собой просто стоимости линий связи.
2. Получить следующую вершину.
Найти следующую вершину, не принадлежащую множеству T и имеющую путь от вершины s с минимальной стоимостью, и включить эту вершину во множество Tи в Дерево.Кроме того, к дереву добавляется ребро, инцидентное этой вершине и вершине множества T,входящей в путь с минимальной стоимостью. Это может быть сформулировано следующим образом. Найти вершину xÏ Ттакую, что
L(x) = min L(j)
jÏT
Добавить вершину хкмножеству Tи к дереву; добавить к дереву ребро, инцидентное вершине х, составляющее компонент пути L(x)с минимальной стоимостью, то есть последний ретрансляционный участок пути.
3. Обновить путь с минимальной стоимостью.
L(n) = min[L(n), L(x) + w(x, п)] для всех пÏ Т.
Если последняя величина минимальна, то с этого момента путь от вершины до вершины ппредставляет собой конкатенацию пути от вершины s до вершины хи пути от вершины х до вершины п.
Алгоритм завершает работу, когда все вершины добавлены к множеству Т. Таким образом, для работы алгоритма требуется |V| итераций. К моменту окончания работы алгоритма значение L(x), поставленное в соответствие каждой вершине x представляет собой минимальную стоимость (длину) пути от вершины sдо вершины х. Кроме того, Деревопредставляет собой связующее дерево исходного ориентированного графа, определяющее пути с минимальной стоимостью от вершины s до всех остальных вершин.
На каждой итерации при выполнении шагов 2 и 3 к множеству Tдобавляется одна новая вершина, а также находится путь с минимальной стоимостью вершины sдо этой вершины. Другими словами, на каждой итерации к множеству добавляется вершина х, а значение L(x)на этот момент времени представляет собой минимальную стоимость пути от вершины s до вершины х. Более того, путь с минимальной стоимостью определяется уникальным путем от вершины s , вершины хво множестве Т. Этот путь проходит только по вершинам, принадлежащим множеству Т. Чтобы понять это, рассмотрим следующую цепочку рассуждений. Вершина х,добавляемая на первой итерации, должна быть смежной с вершиной и не должно существовать другого пути к вершине хс меньшей стоимостью. Если вершина хне является смежной с вершиной s, тогда должна существовать другая вершина, смежная с вершиной s, представляющая собой первый транзитный участок пути с минимальной стоимостью к вершине х. В этом случае при выборе вершины, добавляемой к множеству Т, предпочтение будет отдано этой вершине, а не вершине х. Если вершина х является смежной с вершиной s, но путь s—хне является путем с наименьшей стоимостью от вершины s до вершины х, то это значит, что существует другая смежная с вершиной sвершина у, находящаяся на пути с минимальной стоимостью, и при выборе добавляемой к множеству Твершины предпочтение будет отдано вершине у, а не вершине х. После выполнения kитераций во множество Tвойдут kвершин и будет найден путь с минимальной стоимостью от вершины sдо каждой из этих вершин. Теперь рассмотрим все возможные пути от вершины s до вершин, не входящих в множество Т. Среди этих путей существу один путь с минимальной стоимостью, проходящий исключительно по вершинам, принадлежащим множеству Т, заканчивающийся линией, непосредственно связывающей некую вершину множества Тсвершиной, не принадлежащей множеству Т. Эта вершина добавляется к множеству Т, а соответствующий путь считается путем с наименьшей стоимостью к данной вершине.
В табл. 1 показан результат применения данного алгоритма к графу, представленному на рис.1.
| № | Т | L(2) | Путь | L(3) | Путь | L(4) | Путь | L(5) | Путь | L(6) | Путь |
| 1 | ∞ | - | 5 | 1-3 | ∞ | - | 1 | 1-5 | 5 | 1-6 | |
| 2 | 6 | 1-5-2 | 5  6 | 1-3 1-5-3 | ∞ | - | 1 | 1-5 | 5 | 1-6 | |
| 3 | 6 | 1-5-2 | 5 6 | 1-3 1-5-3 | 9 | 1-5-2-4 | 1 | 1-5 | 5  10 | 1-6 1-5-2-6 | |
| 4 |  11 6 | 1-6-2 1-5-2 | 5 6 18 |   1-3 1-5-3 1-6-2-5-3 | 9  14 | 1-5-2-4 1-6-2-4 | 1 13 |  1-5 1-6-2-5 | 5 10 | 1-6 1-5-2-6 | |
| 5 | 6  11 14 |  1-5-2 1-6-2 1-3-5-2 | 5  6 18 |  1-3 1-5-3 1-6-2-5-3 | 9  14 12 11 17 24 | 1-5-2-4 1-6-2-4 1-5-3-4 1-3-4 1-3-5-2-4 1-6-2-5- | 1  9  13 | 1-5 1-3-5 1-6-2-5 | 5  10 17 | 1-6 1-5-2-6 1-3-5-2-6 | |
| 6 | 6 11 17 18 | 1-5-2 1-6-2 1-3-4-2 1-5-3-4- | 5  11  15 | 1-4-3 1-5-2-4-3 1-6-2-4-3 | 9 | 1-5-2-4 | 1  14 | 1-5 1-3-4-2-5 | 1 21  22 | 1-6 1-3-4-2-6 1-5-3-4-2-6 |
V1 V3
V1 V3
V1 V3
V1 V3
Дан ориентированный граф $G=(V, E)$ с выделенной вершиной $s$. Веса рёбер в графе могут быть любыми. Надо для каждой вершины найти кратчайшее расстояние до неё от $s$.
Ориентированность графа важна, потому что поиск кратчайших путей в неориентированном графе с отрицательными весами рёбер не решается с помощью алгоритма Форда-Беллмана. Но можно свести к поиску паросочетания минимальной стоимости в графе (необязательно двудольном).
Решим эту задачу с помощью динамического программирования:
- $sp[k][v]$ - кратчайшее растояние от $s$ до $v$ по путям, в которых $k$ рёбер.
- Начальные значения
- $ sp[0][s] = 0 $
- $ sp[0][V \setminus \ ] = INF $
- $ sp[1. |V|][*] = INF $
- Ответ: $dist[v] = \min_ sp[k][v]$
- Восстановление ответа: либо запоминаем для каждого состояния, из какого пришли, либо заново перебираем
Заметим, что цикл по вершинам, внутри которого перебираются соседи, можно заменить на цикл по рёбрам и получить
Мы получили решение, в котором используется массив размера $|V| \times |V|$. Мы можем изменить это и получить 2 массива длины $|V|$ - достаточно заметить, что для подсчёта $sp[k][*]$ достаточно знать $sp[k-1][*]$, поэтому нам достаточно хранить только 2 последних слоя динамики.
В предыдущем пункте можно отказаться от двух массивов и оставить только $sp[v]$. Тогда $sp[v] = \min_ sp[u] + w(u, v)$. Однако, теперь значение, хранящееся в $sp[v]$ потеряет то значение, которое мы ему придавали раньше, потому что теперь при пересчёте слоя динамики мы можем воспользоваться значениями из нового слоя.
Однако можно доказать, что за $k$ итераций в $sp[v]$ будут точно рассмотрены пути длины хотя бы $k$ рёбер от $s$ до $v$ (плюс, возможно, пути большей длины) (доказательство по индукции, упражнение читателю). Из этого следует, что за $|V| - 1$ итераций в $sp[v]$ будут рассмотрены все возможные пути из $s$ в $v$ $\implies$ в $sp[v]$ будут будет хранится кратчайшее расстояние от $s$ до $v$.
- Если на какой-то итерации внешнего цикла $sp[*]$ не изменился, то мы уже нашли все кратчайшие расстояния и можно прекратить наш алгоритм.
- Достаточно на каждом шаге рассматривать не все рёбра, а только те, у которых $sp$ изменился хотя бы для одного из концов.
Эти немудрёные рассуждения приводят нас к следующему, окончательному коду:
В графе есть цикл отрицательного веса, достижимый из $s$ $\iff$ после $|V|$-й итерации алгоритма $updated \_ vertices$ непусто.
$\implies$: пусть в графе есть отрицательный цикл $v_0 \rightarrow v_1 \rightarrow \dots \rightarrow v_k = v_0$. Если в этом цикле есть такое ребро $v_i \rightarrow v_$, что на $|V|$-м шаге $sp[v_] > sp[v_] + w(v_, v_)$, то $v_$ окажется в $updated\_ vertices$ и утверждение доказано. Пусть такого ребра нет, то есть $$ \forall i \in [0 \dots k]: sp[v_] \leq sp[v_] + w(v_, v_) $$Сложим эти неравенства и заметим, что $\sum_ sp[v_] = \sum_ sp[v_]$ (поскольку это одна и та же сумма, в которой сделали циклический сдвиг (помним, что $v_k = v_0$)).
Значит, если сократить, получится: $$ 0 \leq \sum_ w(v_, v_) $$
Или, другими словами, наш цикл вовсе не имеет отрицательный вес. Противоречие.
$\impliedby$: если на $|V|$-й итерации расстояние до какой-то вершины уменьшилось, значит существует последовательность из хотя бы $|V|$ рёбер из $s$ в некоторую вершину $v$, вдоль которой расстояние меньше, чем то, что было на $(|V| - 1)$-й итерации. Поскольку рёбер не меньше, чем $|V|$, то в этой последовательности есть цикл. Если этот цикл имеет неотрицательный вес, то его можно выкинуть из последовательности и получить последовательность рёбер меньшей длины, которая должна была быть рассмотрена на предыдущих шагах алгоритма $\implies$ на $|V|$-й итерации расстояние не могло уменьшиться вдоль последовательности с циклом. Значит, цикл всё-таки имеет отрицательный вес, а это ровно то, чего мы хотели. ∎
Из леммы следует, что для проверки наличия цикла отрицательного веса достаточно запустить алгоритм на ещё одну итерацию и проверить, что ничего не изменилось.Чтобы восстановить цикл достаточно для каждой вершины $v$ запоминать $prev[v]$ - вершину, через которую произошла последняя релаксация ребра в $v$. Тогда для восстановления цикла отрицательного веса достаточно взять любое из рёбер, которые прорелаксировались на $|V|$-м шаге и начать от них разматывать цикл.
Корректность этого алгоритма следует из того, что любое ребро, которое прорелаксировалось на $|V|$-м шаге лежит на цикле отрицательного веса $\implies$ пойдя из конца ребра мы вернёмся в него, пройдя по нашему циклу отрицательного веса.
Запускаем алгоритм на $|V|$ шагов. Если на последнем шаге до вершины расстояние не поменялось, то оно и кратчайшее. Если поменялось, то до неё и до всех вершин, достижимых из неё, расстояние от стартовой вершины равно минус бесконечности. Чтобы найти все вершины с расстоянием минус бесконечность, достаточно запустить dfs из всех вершин, расстояние до которых уменьшилось на последней итерации алгоритма.
Алгоритм Форда-Беллмана — это алгоритм поиска кратчайшего пути во взвешенном графе.
Введение
Алгоритм назван в честь учёных из США Ричарда Беллмана и Лестера Форда. Изобретателем основ этого алгоритма по факту является Форд, который вывел его в середине прошлого века при работе с иной математической задачей, в одной из подзадач которой нужно было определить самый короткий путь в графе. Тогда Форд сделал эскиз алгоритма решения такой задачи. А чуть позже Беллман выпустил статью, которая была посвящена именно проблеме определения наикратчайшего пути. В своей работе он дал чёткую и однозначную формулировку алгоритма, и она актуальна и по сей день.
Алгоритм Форда-Беллмана
Предполагается, что граф не имеет циклов с отрицательным весом. Зададим массив расстояний d[0…n – 1], который по завершению выполнения алгоритма содержит итоговый результат. Сначала заполним массив такими данными: d[v] = 0, а другие элементы d[] будут определены как имеющие размер бесконечность. Непосредственно алгоритм Форда-Беллмана состоит из нескольких фаз. Во всех фазах выполняется просмотр всех рёбер графа, и согласно алгоритма делается попытка релаксации (rеlax, ослабления) по направлению каждого ребра (а, b) стоимости с. Релаксация вдоль ребра означает попытку улучшения значения d[b] за счёт значения d[а] + с. По факту это означает попытку улучшения результата для вершины b, используя ребро (а, b) и действующий ответ для вершины a. Заявлено, что хватит n – 1 фазы алгоритма для правильного подсчёта длин всех самых коротких путей в графе (конечно, без циклов с отрицательным весом). Если вершины являются недостижимыми, то дистанция d [] для них так и остаётся бесконечной.
Готовые работы на аналогичную тему
Простая реализация алгоритма
![Простая реализация алгоритма. Автор24 — интернет-биржа студенческих работ]()
Рисунок 1. Простая реализация алгоритма. Автор24 — интернет-биржа студенческих работ
Выполнение проверки "if (d[e[j].a]
Улучшенная реализация алгоритма
Работу алгоритма возможно сделать более быстрой. Часто итоговый результат может быть найден лишь за незначительное число фаз, а остальные фазы работы алгоритма по сути бесполезны и в них в холостую ведётся просмотр остальных рёбер. По этой причине надо сохранять флаг наличия изменений в данной, работающей фазе, и если появилась фаза где нет изменений, то работу алгоритма можно прекращать. Такая модификация существенно ускорит работу алгоритма, особенно при случайных графах. И так же при этой оптимизации нет необходимости контролировать количество фаз алгоритма, его работа прекратится автоматически через необходимое количество фаз.
![Улучшенная реализация алгоритма. Автор24 — интернет-биржа студенческих работ]()
Рисунок 2. Улучшенная реализация алгоритма. Автор24 — интернет-биржа студенческих работ
Восстановить пути
Работу алгоритма Форда-Беллмана возможно преобразовать таким образом, что он будет находить самые короткие маршруты, и, кроме того, выводить и показывать эти самые короткие маршруты. С этой целью создадим добавочный массив р[0…n – 1], который будет служить для сохранения истории, то есть предыдущую вершину в самом коротком маршруте, который ведёт к ней. То есть, самый короткий путь к какой-либо вершине а будет самым коротким маршрутом до какой-либо вершины р[a], к которому добавили в окончание вершину а. Следует отметить, что действие алгоритма Форда-Беллмана следует этой же логической цепи. Алгоритм, полагая, что самый короткий маршрут до одной вершины уже вычислен, делает попытку уменьшить (улучшить) самый короткий маршрут до следующей вершины. Таким образом, при улучшении необходимо просто сохранить в массиве р [], какая вершина вызвала это улучшение.
Вначале выполняется проход по ранее пройденным вершинам, с началом в вершине t, и весь маршрут сохраняется в переменной path. В этой переменной (списке) и будет самый короткий путь.
Доказательство алгоритма
Следует отметить, что алгоритм Форда-Беллмана способен определить маршруты ко всем вершинам, которые возможно достичь, а релаксацию оставшихся вершин он выполнять вообще не будет. Можно доказать, что, когда будут исполнены i фаз алгоритма, будут правильно определены все оптимальные маршруты, которые по длине (по количеству рёбер) не будут превосходить i. Или по-другому, для каждой вершины а будем считать, что К это количество рёбер в самом коротком маршруте к ней. То есть это означает, что после К фаз самый короткий маршрут будет с гарантией определён.
![]()
![]()
![]()
![]()
![]()
![]()
![]()
Шаг 1. Положить и для всех вершин , отличных от . Окрасить вершину и положить .
Шаг 2. Для каждой вершины найти новое значение , где обозначает вес дуги . Окрасить одну из вершин , для которых величина является наименьшей, присоединить эту вершину к . Окрасить также одну из дуг, ведущих из множества окрашенных вершин в выбранную вершину и дающих наименьшее значение для . Если для некоторой окрашенной вершины происходит уменьшение величины , то с этой вершины и инцидентной ей окрашенной дуги окраска снимается.
Шаг 3. Если все вершины окрашены, т.е , и после выполнения шага 2 ни одно из чисел не меняется - конец алгоритма: для любой вершины кратчайший путь из в однозначно определяется, состоит из окрашенных дуг и имеет длину . Иначе перейти к шагу 2. [1; 3]
Алгоритм Беллмана-Форда не решает указанной задачи при наличии в исходном графе контура, имеющего отрицательную длину. Действительно, в этом случае, неограниченное число раз просчитывая этот контур, можно получить путь со сколь угодно малой по величине длиной.
Проанализируем вычислительную сложность алгоритма Беллмана-Форда.
В разделе 2.1 была рассмотрена вычислительная сложность алгоритма Дейкстры, время счёта которого составляет , где - число вершин в орграфе. Так как в алгоритме Дейкстры каждая вершина окрашивается ровно один раз, а в алгоритме Беллмана-Форда она может окрашиваться до раза, то алгоритм Беллмана-Форда имеет время счёта порядка . [3]
Пример - Алгоритм Беллмана-Форда.
Рассмотрим работу алгоритма Беллмана-Форда на примере орграфа, представленного на рисунке 6, при этом найдём кратчайший путь из вершины 1 в каждую вершину данного орграфа.
Читайте также:
