6.2.4 Шаги «2 — 6» расчетов
Выполняются
аналогично расчетам на шаге 1. Особенностью
расчетов во время выполнения шагов 2 —
6 оказалось, что на шаге 5 в табл. 6.3
получено множество из восьми ребер.
Поскольку присоединение дуг
или
формировало бы на подграфе кратчайшего
остова цикл их необходимо отбросить и
остановить выбор на дуге
.
Результаты расчетов на шагах 2 — 6 сведены в табл. 6.3, 6.4. На рис. 6.5 показано изменение по шагам подграфов минимального остова графа G.
6.2.5 Выводы
Таким образом, в результате расчетов по алгоритму Дейкстра сформирован минимальный остов графа G (см. результаты на шаге 6, рис. 6.5) с суммарной длиной дуг — 28.
7 Методические указания по выполнению расчетно-графической работы №3 на тему: «Поиск кратчайших путей на неориентированном графе по алгоритму Флойда»
Задание на расчетно-графическую работу №3
Задание на РГР
формулируется следующим образом: «Найти
кратчайшие пути на неориентированном
графе G
(рис. 7.1) по алгоритму Флойда. Протяженность
(вес) ребра приведены в табл. 7.1 , где
—
означает отсутствие ребра
,
а «1» — его наличие, которое необходимо
умножить на вес ребра. Для вариантов
1—10 ребро
является дугой с направлением от вершины
к
,
для вариантов 11—20 ребро
— дугой с направлением от вершины
к
,
для вариантов 21—30 ребро
— дугой с направлением от вершины
к
,
для вариантов 31—40 ребро
— дугой с направлением от вершины
к
,
для вариантов 41—50 ребро
— дугой с направлением от вершины
к
».
Таблица 7.1 — Данные для формирования графа G по вариантам
Старший разряд номера варианта |
Индексы вершин, инцидентных ребру |
|||||||||
0,1 |
0,2 |
0,3 |
1,3 |
1,4 |
2,3 |
2,5 |
3,4 |
3,5 |
3,6 |
|
Вес ребра (условных единиц) |
||||||||||
7 |
9 |
12 |
6 |
4 |
6 |
7 |
10 |
7 |
11 |
|
1 |
|
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
3 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
4 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
5 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
6 |
|
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
7 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
8 |
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
9 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
|
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Таблица 7.1 — Продолжение
Младший разряд номера варианта |
Индексы вершин, инцидентных ребру |
|||||||||
4,6 |
4,7 |
5,6 |
5,8 |
6,7 |
6,8 |
6,9 |
7,9 |
8,9 |
|
|
Вес ребра (условных единиц) |
||||||||||
2 |
6 |
4 |
9 |
8 |
5 |
4 |
3 |
9 |
|
|
1 |
1 |
1 |
1 |
1 |
|
1 |
|
1 |
1 |
|
2 |
1 |
1 |
1 |
1 |
1 |
|
1 |
|
1 |
|
3 |
1 |
1 |
1 |
1 |
|
1 |
|
1 |
|
|
4 |
1 |
1 |
1 |
1 |
1 |
|
1 |
|
1 |
|
5 |
1 |
1 |
1 |
1 |
|
1 |
|
1 |
|
|
6 |
1 |
1 |
1 |
1 |
1 |
|
1 |
|
1 |
|
7 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
|
|
8 |
1 |
1 |
1 |
1 |
|
1 |
1 |
|
1 |
|
9 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
|
|
0 |
1 |
1 |
1 |
1 |
|
1 |
|
1 |
1 |
|