Партнерка на США и Канаду по недвижимости, выплаты в крипто
- 30% recurring commission
- Выплаты в USDT
- Вывод каждую неделю
- Комиссия до 5 лет за каждого referral
Решение.
1)Изобразим данный граф.
v | 1 | 2 | 3 | 4 | 5 | 6 |
0 |
| |||||
1 | ||||||
3 | ||||||
4 | ||||||
5 | ||||||
6 | ||||||
7 |
Выписываем результаты расчета предок каждой вершины по дереву кратчайших путей
и расстояние из начальной вершины до остальных по графу. 
.
|
|
|
1 | 0 | 0 |
2 | 10 | 4 |
3 | 7 | 1 |
4 | 9 | 3 |
5 | 5 | 6 |
6 | 3 | 1 |
Строим дерево кратчайших путей из начальной вершины
. 
Решаем задачу маршрутизации : для данной конечной вершины
найти кратчайший путь 
, ведущий из начальной вершины в данную. Пусть 
. Двигаемся из конечной вершины в начальную, используя функцию предка 
. 
:=
=2;
;
;
;
-получили 0, путь построен.
Реверсиуем(т. е. записываем в обратном поряке) массив 
: 
.
=
.
Описание алгоритма Дейкстры
Алгоритм Дейкстры:
Дано взвешенный орграф 
и 
-весовая матрица.
Требуется, чтобы 
Результат: Метка 
вершин, если 
не достижима из 
, если
,то 
-длина кратчайшего пути из s в vi.
- указывает на ближайшую к vi вершину на кратчайшем пути из 
в 
, причем
, если
.
Шаг 0 Присвоение начальных значений.
-текущая вершина.
Шаг 1 Обновление меток.
Пусть q-текущая вершина на данном шаге. Для всех 
применить метки в соответствии с выражением.
Причем если
то обновить функцию предшественника : 
Шаг 2 Превращение метки в постоянную.
Среди всех вершин с временными метками найти такую, для которой
Считать метку 
постоянной и принять 
- новая текущая вершина.
Шаг 3 Если q=t, работа алгоритма завершена, найдем кратчайший путь из
в 
.
Если 
перейти к шагу 1.
Если на шаге 2 все вершины помечены как постоянные, Останов
найдены кратчайшие пути из источника s во все вершины графа.
5. Теория графов. Оптимизационные задачи на графах. Алгоритм Флойда нахождения минимальных кратчайших расстояний по графу между всеми парами вершин.
Взвешенный ориентированный граф на пяти вершинах задан массивом ребер:
|
|
| ves(r) |
1 | 1 | 5 | 3 |
2 | 2 | 4 | 1 |
3 | 3 | 5 | 2 |
4 | 2 | 5 | 1 |
5 | 5 | 1 | 6 |
6 | 5 | 4 | 2 |
7 | 4 | 3 | 7 |
8 | 5 | 2 | 10 |
9 | 1 | 3 | 7 |
1)Изобразить данный граф;
2) Построить весовую матрицу 
данного графа.
3) Выполнить алгоритм Флойда (6 итераций) на матрице 
, элементы которой являются записями, состоящими из двух полей: первое поле - это текущее кратчайшее расстояние между парой вершин, второе - первая вершина на таком кратчайшем пути.
4) Использовать полученную структуру для решения задачи маршрутизации:
Для данной начальной вершины 
и конечной вершины 
найти кратчайший путь 
из начальной вершины в данную.
Решение.
Строим весовую матрицу графа и маршрутную матрицу, лбъединив их в одной
∞,1 | ∞,1 | 7,3 | ∞,1 | 3,5 |
∞,2 | ∞,2 | ∞,2 | 1,4 | 1,5 |
∞,3 | ∞,3 | ∞,3 | ∞,3 | 2,5 |
∞,4 | ∞,4 | 7,3 | ∞,4 | ∞,4 |
6,1 | 10,2 | ∞,5 | 2,4 | ∞,5 |
Выполняем 5 этапов алгоритма Флойда используя для оптимизации маршрута вершины 
в качестве промежуточных пунктов.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 |
