Исследование процессов маршрутизации (стр. 2 из 6)
На каждой итерации при выполнении шагов 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 | {1} | ∞ | - | 5 | 1-3 | ∞ | - | 1 | 1-5 | 5 | 1-6 |
| 2 | {1;5} | 6 | 1-5-2 | 5  6 | 1-3 1-5-3 | ∞ | - | 1 | 1-5 | 5 | 1-6 |
| 3 | {1;5;2} | 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 | {1;5;2;6;} |  116 | 1-6-2 1-5-2 | 5 6 18 |   1-31-5-3 1-6-2-5-3 | 9  14 | 1-5-2-4 1-6-2-4 | 1 13 |  1-51-6-2-5 | 5 10 | 1-6 1-5-2-6 |
| 5 | {1;5;2;6;3} | 6  1114 |  1-5-21-6-2 1-3-5-2 | 5  618 |  1-31-5-3 1-6-2-5-3 | 9  1412 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-3-4 | 1  9  13 | 1-5 1-3-5 1-6-2-5 | 5  1017 | 1-6 1-5-2-6 1-3-5-2-6 |
| 6 | {1;5;2;6;3;4} | 6 1117 18 | 1-5-2 1-6-2 1-3-4-2 1-5-3-4-2 | 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 |
Рисунок. 2
V1
V3Рисунок.3
V1
V3Рисунок.4
V1
V3Рисунок.5
V1
V3Рисунок.6
V1
V3Рисунок.7
V1
V31.3.Алгоритм Беллмана-Форда
Алгоритм Беллмана — Форда может быть сформулирован следующим образом. Требуется найти кратчайшие пути от заданной вершины при условии, что эти пути состоят максимум из одного ребра, затем найти кратчайшие пути при условии, что эти пути состоят максимум из двух ребер, и т. д. Этот алгоритм также работает поэтапно, формально он может быть определен следующим образом. Введем обозначения:
· s — вершина-источник;
· w(i,j) — стоимость линии от вершины i до вершины j, причем w(i, j)= 0 или w(i,j)=¥, если две вершины не соединены напрямую, и w(i,j) =>0, если две вершины соединены напрямую;
· h — максимальное количество ребер в пути на текущем шаге алгоритма;
· Lh(n) — минимальная стоимость пути от вершины sдо вершины ппри условии, что этот путь состоит не более чем из hребер.
Алгоритм состоит из двух шагов. Шаг 2 повторяется до тех пор, пока стоимости путей не перестанут изменяться.
1. Инициализация:
L0(n) = ¥ для всех п ¹s,
Lh(s) = 0 для всех h.
2. Обновление.Для каждого последовательного h>= 0 и для каждого п ¹sвычислить
Lh+1(n) - min[Lh(j) + w(j, n)].
j
Соединить вершину п с предыдущей вершиной j, для которой находится минимальное значение, и удалить любое соединение вершины пс предыдущей вершиной, образованное на более ранней итерации. Путь от вершины sдо вершины пзаканчивается линией связи от вершины j до вершины п.