Лабораторная работа №1

«Изучение методов организации оптимальных маршрутов передачи информации в инфокоммуникационных средах»

Цель работы: изучение и исследование свойств методов Дейкстры, Форда-Фалкерсона и метода динамического программирования для решения задач организации оптимальных маршрутов передачи информации в инфокоммуникационных средах.

 

Отчет по работе должен содержать:

¨ цель работы;

¨ номер и исходные данные варианта;

¨ ход решения и промежуточные расчеты;

¨ выводы по проделанной работе: провести сравнительный анализ изученных методов Дейкстры, Форда-Фалкерсона, метода динамического программирования по областям практических приложений, удобства и эффективности использования персоналом, возможности автоматизации и алгоритмизации процедур метода. Оцените вычислительную сложность использованных методов.

Вариант №1 (Кузнецов)

l ₁ = 10;       l ₂ = 7;         l ₃ = 12;       l ₄ = 7;         l ₅ = 9;

l ₆ = 14;       l ₇ = 11;       l ₈ = 5;        l ₉ = 13;       l ₁₀ = 10;

l ₁₁ = 16;      l ₁₂ =7;         l ₁₃ = 8;        l ₁₄ = 6;        l ₁₅ = 7;

l ₁₆ =5;         l ₁₇ =9.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

Вариант №2 (Бурмакин)

l ₁ = 21;       l ₂ = 13;       l ₃ = 10;       l ₄ = 18;       l ₅ = 14;

l ₆ = 19;       l ₇ = 15;       l ₈ = 5;         l ₉ = 13;       l ₁₀ = 10;

l ₁₁ = 16;      l ₁₂ =7;         l ₁₃ = 8;        l ₁₄ = 6;        l ₁₅ = 7;

l ₁₆ =12;       l ₁₇ =9.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

 

Вариант №3 (Даревский)

l ₁ = 10;       l ₂ = 7;         l ₃ = 20;       l ₄ = 7;         l ₅ = 9;

l ₆ = 14;       l ₇ = 19;       l ₈ = 11;       l ₉ = 13;       l ₁₀ = 10;

l ₁₁ = 16;      l ₁₂ =7;         l ₁₃ = 8;        l ₁₄ = 6;        l ₁₅ =9;

l ₁₆ =5;         l ₁₇ =12.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

 

Вариант №4 (Жуков)

l ₁ = 10;       l ₂ = 25;       l ₃ = 12;       l ₄ = 28;       l ₅ = 17;

l ₆ = 14;       l ₇ = 11;       l ₈ = 5;         l ₉ = 13;       l ₁₀ = 10;

l ₁₁ = 16;      l ₁₂ =21;       l ₁₃ = 826     l ₁₄ = 6;        l ₁₅ = 24;

l ₁₆ =22;       l ₁₇ =15;       l ₁₈= 12;       l ₁₉= 10;       l ₂₀= 16.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

Вариант №5 (Кузнецова)

l ₁ = 10;       l ₂ = 30;       l ₃ = 12;       l ₄ = 14;       l ₅ = 26;

l ₆ = 14;       l ₇ = 11;       l ₈ = 14;       l ₉ = 13;       l ₁₀ = 10;

l ₁₁ = 16;      l ₁₂ =22;       l ₁₃ = 8;        l ₁₄ =12;       l ₁₅ =21;

l ₁₆ =16;       l ₁₇ =9;         l ₁₈= 17;       l ₁₉ = 8.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

Вариант №6 (Корниенко)

l ₁ = 18;       l ₂ = 4;         l ₃ = 12;       l ₄ = 7;         l ₅ = 13;

l ₆ = 18;       l ₇ = 11;       l ₈ = 9;         l ₉ = 13;       l ₁₀ = 10;

l ₁₁ = 16;      l ₁₂ = 12;      l ₁₃ = 19;      l ₁₄ = 6;        l ₁₅ = 7;

l ₁₆ = 19;      l ₁₇ = 15;      l ₁₈= 12.

Для заданного графа определите:

1) кратчайшие пути от вершины 5 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 5 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

Вариант №7 (Логинов)

l ₁ = 28;       l ₂ = 14;       l ₃ = 24;       l ₄ = 30;       l ₅ = 18;

l ₆ = 24;       l ₇ = 16;       l ₈ = 25;       l ₉ = 32;       l ₁₀ = 20;

l ₁₁ = 16;      l ₁₂ =17;       l ₁₃ = 8;        l ₁₄ = 22;      l ₁₅ = 7;

l ₁₆ =25;       l ₁₇ =21.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

Вариант №8 (Романов)

l ₁ = 32;       l ₂ = 15;       l ₃ = 24;       l ₄ = 13;       l ₅ = 18;

l ₆ = 21;       l ₇ = 18;       l ₈ = 22;       l ₉ = 16;       l ₁₀ = 30;

l ₁₁ = 16;      l ₁₂ =24;       l ₁₃ = 15;      l ₁₄ = 14;      l ₁₅ = 18;

l ₁₆ =25        l ₁₇ =9.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

 

Вариант №9 (Сентюрина)

l ₁ = 10;       l ₂ = 24;       l ₃ = 12;       l ₄ = 27;       l ₅ = 16;

l ₆ = 19;       l ₇ = 21;       l ₈ = 13;       l ₉ = 13;       l ₁₀ = 10;

l ₁₁ = 16;      l ₁₂ =25;       l ₁₃ = 8;        l ₁₄ = 23;      l ₁₅ = 14;

l ₁₆ =18;       l ₁₇ = 19.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

 

Вариант №10 (Соболев)

l ₁ = 32;       l ₂ = 28;       l ₃ = 12;       l ₄ = 18;       l ₅ = 21;

l ₆ = 18;       l ₇ = 11;       l ₈ = 15;       l ₉ = 27;       l ₁₀ = 10;

l ₁₁ = 16;      l ₁₂ = 9;        l ₁₃ = 19;      l ₁₄ = 6;        l ₁₅ = 27;

l ₁₆ = 22;      l ₁₇ =11;       l ₁₈= 20;       l ₁₉ = 17;      l ₂₀ = 18.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

Вариант №11 (Сатылбадиев)

l ₁ = 18;       l ₂ = 14;       l ₃ = 20;       l ₄ = 24;       l ₅ = 19;

l ₆ = 14;       l ₇ = 11;       l ₈ = 11;       l ₉ = 13;       l ₁₀ = 10;

l ₁₁ = 16;      l ₁₂ =9;         l ₁₃ = 17;      l ₁₄ = 6;        l ₁₅ =23;

l ₁₆ =21;       l ₁₇ =13;       l ₁₈ =15;       l ₁₉ =15.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

Вариант №12 (Савенко)

l ₁ = 15;       l ₂ = 13;       l ₃ = 19;       l ₄ = 22;       l ₅ = 14;

l ₆ = 25;       l ₇ = 28;       l ₈ = 17;       l ₉ = 10;       l ₁₀ = 19;

l ₁₁ = 16;      l ₁₂ =21;       l ₁₃ = 8;        l ₁₄ = 16;      l ₁₅ = 7;

l ₁₆ =25        l ₁₇ = 21;      l ₁₈ =17;       l ₁₉ =13.

Для заданного графа определите:

1) кратчайшие пути от вершины 5 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 5 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

 

Вариант №13 (Степаненко)

l ₁ = 30;       l ₂ = 28;       l ₃ = 34;       l ₄ = 41;       l ₅ = 27;

l ₆ = 21;       l ₇ = 31;       l ₈ = 37;       l ₉ = 29;       l ₁₀ = 35;

l ₁₁ = 26;      l ₁₂ = 33;      l ₁₃ = 25;      l ₁₄ = 20;      l ₁₅ = 17;

l ₁₆ =18;       l ₁₇ = 26;      l ₁₈ = 28.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

Вариант №14 (Толстобров)

l ₁ = 45;       l ₂ = 29;       l ₃ = 37;       l ₄ = 22;       l ₅ = 38;

l ₆ = 31;       l ₇ = 45;       l ₈ = 29;       l ₉ = 24;       l ₁₀ = 42;

l ₁₁ = 36;      l ₁₂ = 25;      l ₁₃ = 28;      l ₁₄ = 36;      l ₁₅ = 45;

l ₁₆ =41;       l ₁₇ = 36.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

Вариант №15 (Хорошенко)

l ₁ = 48;       l ₂ = 18;       l ₃ = 30;       l ₄ = 25;       l ₅ = 45;

l ₆ = 23;       l ₇ = 38;       l ₈ = 42;       l ₉ = 24;       l ₁₀ = 27;

l ₁₁ = 46;      l ₁₂ = 41;      l ₁₃ = 38;      l ₁₄ = 31;      l ₁₅ = 34;

l ₁₆ =29;       l ₁₇ = 39.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

Вариант №16 (Шейко)

l ₁ = 40;       l ₂ = 34;       l ₃ = 21;       l ₄ = 18;       l ₅ = 48;

l ₆ = 26;       l ₇ = 54;       l ₈ = 24;       l ₉ = 36;       l ₁₀ = 30;

l ₁₁ = 32;      l ₁₂ = 23;      l ₁₃ = 28;      l ₁₄ = 41;      l ₁₅ = 35;

l ₁₆ =29;       l ₁₇ = 26;      l ₁₈ = 28;      l ₁₉ = 44;      l ₂₀= 32.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

Вариант №17 (Шуляков)

l ₁ = 27;       l ₂ = 24;       l ₃ = 21;       l ₄ = 18;       l ₅ = 36;

l ₆ = 26;       l ₇ = 54;       l ₈ = 42;       l ₉ = 36;       l ₁₀ = 24;

l ₁₁ = 18;      l ₁₂ = 23;      l ₁₃ = 28;      l ₁₄ = 41;      l ₁₅ = 35;

l ₁₆ =29;       l ₁₇ = 16;      l ₁₈ = 28;      l ₁₉ = 27.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

Вариант №18 (Маметов)

l ₁ = 27;       l ₂ = 20;       l ₃ = 19;       l ₄ = 31;       l ₅ = 35;

l ₆ = 43;       l ₇ = 17;       l ₈ = 28;       l ₉ = 31;       l ₁₀ = 41;

l ₁₁ = 25;      l ₁₂ = 16;      l ₁₃ = 45;      l ₁₄ = 24;      l ₁₅ = 26;

l ₁₆ =38;       l ₁₇ = 40;      l ₁₈ = 28;      l ₁₉ = 32.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 5 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

 

Вариант №19 (Заблотский)

l ₁ = 54;       l ₂ = 48;       l ₃ = 53;       l ₄ = 63;       l ₅ = 56;

l ₆ = 37;       l ₇ = 45;       l ₈ = 37;       l ₉ = 40;       l ₁₀ = 32;

l ₁₁ = 42;      l ₁₂ = 41;      l ₁₃ = 28;      l ₁₄ = 50;      l ₁₅ = 36;

l ₁₆ =29;       l ₁₇ = 42.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

 

Вариант №20 (Колыхалин)

l ₁ = 15;       l ₂ = 22;       l ₃ = 18;       l ₄ = 26;       l ₅ = 31;

l ₆ = 19;       l ₇ = 41;       l ₈ = 29;       l ₉ = 22;       l ₁₀ = 24;

l ₁₁ = 34;      l ₁₂ = 16;      l ₁₃ = 25;      l ₁₄ = 40;      l ₁₅ = 28;

l ₁₆ =29;       l ₁₇ = 35.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

 

Вариант №21 (Фирсов)

l ₁ = 33;       l ₂ = 26;       l ₃ = 48;       l ₄ = 27;       l ₅ = 34;

l ₆ = 26;       l ₇ = 18;       l ₈ = 40;       l ₉ = 29;       l ₁₀ = 32

l ₁₁ = 32;      l ₁₂ = 18;      l ₁₃ = 21;      l ₁₄ = 34;      l ₁₅ = 35;

l ₁₆ = 45;      l ₁₇ = 26.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

Вариант №22 (Серафименко)

l ₁ = 27;       l ₂ = 38;       l ₃ = 26;       l ₄ = 26;       l ₅ = 55;

l ₆ = 26;       l ₇ = 54;       l ₈ = 24;       l ₉ = 36;       l ₁₀ = 38;

l ₁₁ = 36;      l ₁₂ = 51;      l ₁₃ = 28;      l ₁₄ = 35;      l ₁₅ = 35;

l ₁₆ =29;       l ₁₇ = 46;      l ₁₈ = 27;      l ₁₉ = 24;      l ₂₀ = 42.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

Вариант №23 (Бижан)

l ₁ = 50;       l ₂ = 34;       l ₃ = 31;       l ₄ = 58;       l ₅ = 48;

l ₆ = 56;       l ₇ = 74;       l ₈ = 44;       l ₉ = 34;       l ₁₀ = 40;

l ₁₁ = 37;      l ₁₂ = 53;      l ₁₃ = 78;      l ₁₄ = 51;      l ₁₅ = 45;

l ₁₆ =29;       l ₁₇ = 27.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

Вариант №24 (Телирбеков)

l ₁ = 58;       l ₂ = 44;       l ₃ = 32;       l ₄ = 38;       l ₅ = 48;

l ₆ = 21;       l ₇ = 39;       l ₈ = 49;       l ₉ = 27;       l ₁₀ = 30;

l ₁₁ = 32;      l ₁₂ = 34;      l ₁₃ = 42;      l ₁₄ = 47;      l ₁₅ = 40;

l ₁₆ =34;       l ₁₇ = 26.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

 

Вариант №25 (Якименко)

l ₁ = 73;       l ₂ = 34;       l ₃ = 42;       l ₄ = 44;       l ₅ = 48;

l ₆ = 59;       l ₇ = 67;       l ₈ = 58;       l ₉ = 36;       l ₁₀ = 39;

l ₁₁ = 32;      l ₁₂ = 23;      l ₁₃ = 38;      l ₁₄ = 41;      l ₁₅ = 35;

l ₁₆ =29;       l ₁₇ = 35.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.

 

Вариант №26 (Маяцкий)

l ₁ = 8;         l ₂ = 34;       l ₃ = 21;       l ₄ = 9;        l ₅ = 25;

l ₆ = 14;       l ₇ = 14;       l ₈ = 24;       l ₉ = 36;       l ₁₀ = 11;

l ₁₁ = 32;      l ₁₂ = 23;      l ₁₃ = 17;      l ₁₄ = 19;      l ₁₅ = 21;

l ₁₆ =19;       l ₁₇ = 26;      l ₁₈ = 28;      l ₁₉ = 18;      l ₂₀ = 32.

Для заданного графа определите:

1) кратчайшие пути от вершины 1 ко всем остальным, используя алгоритм Дейкстры;

2) максимальный поток от вершины 1 к вершине 9, используя алгоритм Форда и Фалкерсона.