Задание
Задание на РГР формулируется следующим
образом: «Найти кратчайший остов
неориентированного графа G
(рисунок 7.5) по алгоритму Дейкстра.
Протяженность (вес) ребер приведены в
таблице 7.4, где
- означает отсутствие ребра (
),
а «1» - его наличие, которое необходимо
умножить на вес ребра. Для вариантов 1
–10 начальной вершиной является
,
для вариантов 11 – 20 – вершина
,
для вариантов 21 – 30 – вершина
,
для вариантов 31 – 40 – вершина
,
для вариантов 41 – 50 – вершина
».
Рисунок 7.1 ― Неориентированный граф G
Таблица 7.4 ― Данные для формирования графа 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 |
1 |
2 |
1 |
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 |
1 |
5 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
6 |
|
1 |
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 |
1 |
9 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Таблица 7.4 ― Продолжение
Младший разряд номера варианта |
Индексы вершин, инцидентных ребру |
|||||||||
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 |
1 |
|
2 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
3 |
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 |
|
6 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
7 |
1 |
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 |
|