«Изучение методов организации оптимальных маршрутов передачи информации в инфокоммуникационных средах»
Цель работы: изучение и исследование свойств методов Дейкстры, Форда-Фалкерсона и метода динамического программирования для решения задач организации оптимальных маршрутов передачи информации в инфокоммуникационных средах.
Отчет по работе должен содержать:
¨ цель работы;
¨ номер и исходные данные варианта;
¨ ход решения и промежуточные расчеты;
¨ выводы по проделанной работе: провести сравнительный анализ изученных методов Дейкстры, Форда-Фалкерсона, метода динамического программирования по областям практических приложений, удобства и эффективности использования персоналом, возможности автоматизации и алгоритмизации процедур метода. Оцените вычислительную сложность использованных методов.
Вариант №1 (Кузнецов)
l 1 = 10; l 2 = 7; l 3 = 12; l 4 = 7; l 5 = 9;
l 6 = 14; l 7 = 11; l 8 = 5; l 9 = 13; l 10 = 10;
l 11 = 16; l 12 =7; l 13 = 8; l 14 = 6; l 15 = 7;
|
|
l 16 =5; l 17 =9.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №2 (Бурмакин)
l 1 = 21; l 2 = 13; l 3 = 10; l 4 = 18; l 5 = 14;
l 6 = 19; l 7 = 15; l 8 = 5; l 9 = 13; l 10 = 10;
l 11 = 16; l 12 =7; l 13 = 8; l 14 = 6; l 15 = 7;
l 16 =12; l 17 =9.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №3 (Даревский)
l 1 = 10; l 2 = 7; l 3 = 20; l 4 = 7; l 5 = 9;
l 6 = 14; l 7 = 19; l 8 = 11; l 9 = 13; l 10 = 10;
l 11 = 16; l 12 =7; l 13 = 8; l 14 = 6; l 15 =9;
l 16 =5; l 17 =12.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №4 (Жуков)
l 1 = 10; l 2 = 25; l 3 = 12; l 4 = 28; l 5 = 17;
l 6 = 14; l 7 = 11; l 8 = 5; l 9 = 13; l 10 = 10;
l 11 = 16; l 12 =21; l 13 = 826 l 14 = 6; l 15 = 24;
l 16 =22; l 17 =15; l 18= 12; l 19= 10; l 20= 16.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №5 (Кузнецова)
|
|
l 1 = 10; l 2 = 30; l 3 = 12; l 4 = 14; l 5 = 26;
l 6 = 14; l 7 = 11; l 8 = 14; l 9 = 13; l 10 = 10;
l 11 = 16; l 12 =22; l 13 = 8; l 14 =12; l 15 =21;
l 16 =16; l 17 =9; l 18= 17; l 19 = 8.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №6 (Корниенко)
l 1 = 18; l 2 = 4; l 3 = 12; l 4 = 7; l 5 = 13;
l 6 = 18; l 7 = 11; l 8 = 9; l 9 = 13; l 10 = 10;
l 11 = 16; l 12 = 12; l 13 = 19; l 14 = 6; l 15 = 7;
l 16 = 19; l 17 = 15; l 18= 12.
Для заданного графа определите:
1) кратчайшие пути от вершины 5 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 5 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №7 (Логинов)
l 1 = 28; l 2 = 14; l 3 = 24; l 4 = 30; l 5 = 18;
l 6 = 24; l 7 = 16; l 8 = 25; l 9 = 32; l 10 = 20;
l 11 = 16; l 12 =17; l 13 = 8; l 14 = 22; l 15 = 7;
l 16 =25; l 17 =21.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №8 (Романов)
l 1 = 32; l 2 = 15; l 3 = 24; l 4 = 13; l 5 = 18;
l 6 = 21; l 7 = 18; l 8 = 22; l 9 = 16; l 10 = 30;
l 11 = 16; l 12 =24; l 13 = 15; l 14 = 14; l 15 = 18;
l 16 =25 l 17 =9.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №9 (Сентюрина)
l 1 = 10; l 2 = 24; l 3 = 12; l 4 = 27; l 5 = 16;
l 6 = 19; l 7 = 21; l 8 = 13; l 9 = 13; l 10 = 10;
l 11 = 16; l 12 =25; l 13 = 8; l 14 = 23; l 15 = 14;
l 16 =18; l 17 = 19.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №10 (Соболев)
l 1 = 32; l 2 = 28; l 3 = 12; l 4 = 18; l 5 = 21;
l 6 = 18; l 7 = 11; l 8 = 15; l 9 = 27; l 10 = 10;
l 11 = 16; l 12 = 9; l 13 = 19; l 14 = 6; l 15 = 27;
l 16 = 22; l 17 =11; l 18= 20; l 19 = 17; l 20 = 18.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №11 (Сатылбадиев)
l 1 = 18; l 2 = 14; l 3 = 20; l 4 = 24; l 5 = 19;
l 6 = 14; l 7 = 11; l 8 = 11; l 9 = 13; l 10 = 10;
l 11 = 16; l 12 =9; l 13 = 17; l 14 = 6; l 15 =23;
l 16 =21; l 17 =13; l 18 =15; l 19 =15.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №12 (Савенко)
l 1 = 15; l 2 = 13; l 3 = 19; l 4 = 22; l 5 = 14;
l 6 = 25; l 7 = 28; l 8 = 17; l 9 = 10; l 10 = 19;
l 11 = 16; l 12 =21; l 13 = 8; l 14 = 16; l 15 = 7;
l 16 =25 l 17 = 21; l 18 =17; l 19 =13.
Для заданного графа определите:
1) кратчайшие пути от вершины 5 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 5 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №13 (Степаненко)
l 1 = 30; l 2 = 28; l 3 = 34; l 4 = 41; l 5 = 27;
l 6 = 21; l 7 = 31; l 8 = 37; l 9 = 29; l 10 = 35;
l 11 = 26; l 12 = 33; l 13 = 25; l 14 = 20; l 15 = 17;
l 16 =18; l 17 = 26; l 18 = 28.
Для заданного графа определите:
|
|
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №14 (Толстобров)
l 1 = 45; l 2 = 29; l 3 = 37; l 4 = 22; l 5 = 38;
l 6 = 31; l 7 = 45; l 8 = 29; l 9 = 24; l 10 = 42;
l 11 = 36; l 12 = 25; l 13 = 28; l 14 = 36; l 15 = 45;
l 16 =41; l 17 = 36.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №15 (Хорошенко)
l 1 = 48; l 2 = 18; l 3 = 30; l 4 = 25; l 5 = 45;
l 6 = 23; l 7 = 38; l 8 = 42; l 9 = 24; l 10 = 27;
l 11 = 46; l 12 = 41; l 13 = 38; l 14 = 31; l 15 = 34;
l 16 =29; l 17 = 39.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №16 (Шейко)
l 1 = 40; l 2 = 34; l 3 = 21; l 4 = 18; l 5 = 48;
l 6 = 26; l 7 = 54; l 8 = 24; l 9 = 36; l 10 = 30;
l 11 = 32; l 12 = 23; l 13 = 28; l 14 = 41; l 15 = 35;
l 16 =29; l 17 = 26; l 18 = 28; l 19 = 44; l 20= 32.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №17 (Шуляков)
l 1 = 27; l 2 = 24; l 3 = 21; l 4 = 18; l 5 = 36;
l 6 = 26; l 7 = 54; l 8 = 42; l 9 = 36; l 10 = 24;
l 11 = 18; l 12 = 23; l 13 = 28; l 14 = 41; l 15 = 35;
l 16 =29; l 17 = 16; l 18 = 28; l 19 = 27.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №18 (Маметов)
l 1 = 27; l 2 = 20; l 3 = 19; l 4 = 31; l 5 = 35;
l 6 = 43; l 7 = 17; l 8 = 28; l 9 = 31; l 10 = 41;
|
|
l 11 = 25; l 12 = 16; l 13 = 45; l 14 = 24; l 15 = 26;
l 16 =38; l 17 = 40; l 18 = 28; l 19 = 32.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 5 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №19 (Заблотский)
l 1 = 54; l 2 = 48; l 3 = 53; l 4 = 63; l 5 = 56;
l 6 = 37; l 7 = 45; l 8 = 37; l 9 = 40; l 10 = 32;
l 11 = 42; l 12 = 41; l 13 = 28; l 14 = 50; l 15 = 36;
l 16 =29; l 17 = 42.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №20 (Колыхалин)
l 1 = 15; l 2 = 22; l 3 = 18; l 4 = 26; l 5 = 31;
l 6 = 19; l 7 = 41; l 8 = 29; l 9 = 22; l 10 = 24;
l 11 = 34; l 12 = 16; l 13 = 25; l 14 = 40; l 15 = 28;
l 16 =29; l 17 = 35.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №21 (Фирсов)
l 1 = 33; l 2 = 26; l 3 = 48; l 4 = 27; l 5 = 34;
l 6 = 26; l 7 = 18; l 8 = 40; l 9 = 29; l 10 = 32
l 11 = 32; l 12 = 18; l 13 = 21; l 14 = 34; l 15 = 35;
l 16 = 45; l 17 = 26.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №22 (Серафименко)
l 1 = 27; l 2 = 38; l 3 = 26; l 4 = 26; l 5 = 55;
l 6 = 26; l 7 = 54; l 8 = 24; l 9 = 36; l 10 = 38;
l 11 = 36; l 12 = 51; l 13 = 28; l 14 = 35; l 15 = 35;
l 16 =29; l 17 = 46; l 18 = 27; l 19 = 24; l 20 = 42.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №23 (Бижан)
l 1 = 50; l 2 = 34; l 3 = 31; l 4 = 58; l 5 = 48;
l 6 = 56; l 7 = 74; l 8 = 44; l 9 = 34; l 10 = 40;
l 11 = 37; l 12 = 53; l 13 = 78; l 14 = 51; l 15 = 45;
l 16 =29; l 17 = 27.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №24 (Телирбеков)
l 1 = 58; l 2 = 44; l 3 = 32; l 4 = 38; l 5 = 48;
l 6 = 21; l 7 = 39; l 8 = 49; l 9 = 27; l 10 = 30;
l 11 = 32; l 12 = 34; l 13 = 42; l 14 = 47; l 15 = 40;
l 16 =34; l 17 = 26.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №25 (Якименко)
l 1 = 73; l 2 = 34; l 3 = 42; l 4 = 44; l 5 = 48;
l 6 = 59; l 7 = 67; l 8 = 58; l 9 = 36; l 10 = 39;
l 11 = 32; l 12 = 23; l 13 = 38; l 14 = 41; l 15 = 35;
l 16 =29; l 17 = 35.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.
Вариант №26 (Маяцкий)
l 1 = 8; l 2 = 34; l 3 = 21; l 4 = 9; l 5 = 25;
l 6 = 14; l 7 = 14; l 8 = 24; l 9 = 36; l 10 = 11;
l 11 = 32; l 12 = 23; l 13 = 17; l 14 = 19; l 15 = 21;
l 16 =19; l 17 = 26; l 18 = 28; l 19 = 18; l 20 = 32.
Для заданного графа определите:
1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;
2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.