Материал: АиСД. Практикум (in dev)

45. Требования к отчету

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

1. Конспект лабораторной работы;

2. Схемы алгоритмов определения в графе кратчайшего расстояния между заданными вершинами для метода динамического программирования и метода Дейкстры;

3. Результаты выполнения работы;

4. Выводы по работе.

Контрольные вопросы

1. Какова теоретическая сложность алгоритмов, рассмотренных в данной работе?

2. В решении каких прикладных задач используется алгоритмы определение в графе кратчайших расстояний между заданными вершинами?

3. Может ли быть применен рассмотренный в работе алгоритм Дейкстры к определению кратчайшего расстояния в ориентированном графе?

4. Как работает алгоритм Дейкстры?

5. Как работает алгоритм динамического программирования применительно к задаче определения в графе кратчайших расстояний между вершинами?

46. Варианты заданий

1. Задание 1: Найти кратчайший путь на графе между тремя парами вершин методом динамического программирования

Варианты Граф

1, 13

2, 14

3 , 15

4, 16

5, 17, 25

6 , 18

7, 19

8, 20

9 ; 21

10; 22

1 1; 23

1 2; 24

2. Задание 2: Найти кратчайший путь между тремя парами вершин методом Дейкстры

1 ; 24

2 ; 23

3 ; 22

4 ; 21

5 ; 20

6; 19

7 ; 18

8; 17

9 ; 16

1 0; 15; 25

1 1; 14

12; 13

47. Решение задач

Задание 1. Дана карта автомобильных дорог. Найти кратчайший путь, учитывая длины дорог, из Ярославля до Новосибирска. Использовать только те города, которые отмечены флажком. Совпадет ли кратчайший маршрут, если не брать во внимание длины дорог?

Задание 2. Дана карта Европы. Турагенству необходимо найти кратчайший туристический маршрут между произвольно выбранными странами Европы.

Задание 4. На участке 3 дома и 3 колодца. От каждого дома к каждому колодцу ведет тропинка. Когда владельцы домов поссорились, они задумали проложить дорогу от каждого дома к каждому колодцу так, чтобы не встречаться на пути к колодцам. Может ли осуществиться их намерение?

48. Задание на разработку программы

Разработка программу для нахождения кратчайшего пути

Вариант 1. Путь из 1 в 9

Вариант 2. Путь из 2 в 5

Вариант 5. Путь из 2 в 7

Вариант 11. Путь из 2 в 7

Вариант 17. Путь из 2 в 7