На этой странице представлены несколько исправленных упражнений по задачам о кратчайшем пути. Упражнения в основном касаются кратчайшего пути для одного источника и кратчайшего пути из многих источников.

Упражнение 1

Авиакомпания Europa обслуживает различные европейские города. В таблице ниже указано время полета между этими городами.
• Как определить самый быстрый маршрут между двумя городами?
• Как изменить предыдущий метод, чтобы учесть продолжительность остановок в разных городах?

 

В

Б

ПРОТИВ

Д

Е

В

 

1:30

2:00

 

2ч15

Б

1:40

 

 

 

3:00

ПРОТИВ

2:20

 

 

2ч55

 

Д

 

 

3:20

 

1ч05

Е

2:25

3ч10

1ч10

 

 

Просто начертите граф, вершинами которого являются города, а дугами — маршруты компании, оценив длину каждой дуги соответствующего рейса. Затем алгоритм кратчайшего пути решает проблему.
Чтобы учесть продолжительность остановок, два методы возможны: Изменить предыдущий алгоритм, включив в дуги стоимость остановки ИЛИ: каждая вершина дублируется; дуга между ними является остановкой соответствующего города.

исправлены упражнения на задачи кратчайшего пути

Упражнение 2

Мы хотим построить новый завод в следующей сети, где узлы — это места, а ссылки — затраты на передачу энергии из одного места в другое:

исправлены упражнения на задачи кратчайшего пути

На основе Дейкстра алгоритм, предлагает способ найти лучшее место для постройки завода, а затем решить проблему с помощью вашего метода. Решить проблему с Флойд-Уоршалл алгоритм.

Мы должны вычислить Дейкстру для каждого узла (в исходном узле). После создания дерева путей просуммируйте стоимость всех путей от любого узла к исходному узлу (суммируйте массив последних кратчайших путей). Лучшее место — это минимальный суммарный вес всех вхождений Дейкстры. С Флойдом-Уоршаллом матрица псевдозамыкания содержит все массивы, просто суммируйте входные данные каждого массива и найдите минимум.

Упражнение 3

Робот движется в следующей среде. Начинается с узла, обозначенного Начало и должен достичь помеченного узла конец. Окружающая среда непрерывна, и шкала представлена на рисунке. Считая робота точкой, каков кратчайший путь от начала до конца.

исправлены упражнения на задачи кратчайшего пути

Вычислите евклидово расстояние между узлами. Нарисуйте граф и примените алгоритм Дейсктры, чтобы найти кратчайший путь от узла «Звезда» к узлу «Конец». Затем нарисуйте путь на рисунке.

кратчайший путь

Начинать

1

2

3

Конец

положить начало

0

ниже

ниже

ниже

ниже

Начинать

кв 5

кв 29

ниже

ниже

1

кв 29

кв 5+ кв 26

ниже

2

кв 5+ кв 26

кв 29 + кв 17

3

кв 29 + кв 17

Кратчайший путь Start-2-End.

Упражнение 4

На графе из упражнения 1 ребра направлены слева направо (или сверху вниз), а веса уменьшены на 4. Как найти минимальный путь из A в F? Реши.

Подать заявление Бельман на этом графике (узел заблокирован, только если все его предшественники заблокированы).

исправлены упражнения на задачи кратчайшего пути

 

В

Б

ПРОТИВ

Д

Е

Ф

положить начало

0

ниже

ниже

ниже

ниже

ниже

А.0

-1

1

5

ниже

ниже

Б, -1

-2

-1

2

ниже

С, -2

-4

0

ниже

Д, -4

-6

-6

Е, -6

-6

Ф

Упражнение 5

(a) Вычислите кратчайший путь из s во все остальные вершины, используя алгоритм Дейкстры. Определить дерево кратчайших путей.

б) Единственно ли дерево кратчайших путей?

(c) Теперь измените вес ребра (3, 4) на −2. Покажите, что в этом случае алгоритм Дейкстры не работает.

исправлены упражнения на задачи кратчайшего пути

а) Решение дается следующей картинкой. Числа рядом с вершинами — это расстояния до начальных вершин, а зачеркивание числа означает, что произошло обновление. Цифры в квадратах обозначают конечные расстояния (кратчайшие расстояния).

исправлены упражнения на задачи кратчайшего пути

(b) Ни одно дерево кратчайших путей не является уникальным. Заменив ребро (s, 3) на ребро (1, 2), можно получить другое дерево кратчайших путей.

(c) Алгоритм Дейкстры даст то же решение, что и в части (a), хотя путь (s, 1, 2, 3, 4) (dist 5) имеет более короткое расстояние, чем путь (s, 1, 4) ( расстояние 6). Вот что происходит: после посещения вершин s, 1, 2 алгоритм ищет кратчайший путь к еще не посещенной вершине. Это будет вершина 4 с расстоянием 6. После посещения вершины 4 алгоритм не будет обновлять вершину 4, поскольку она уже была посещена, и по этой причине не найдет кратчайший путь (расстояние 5).

Упражнение 6

Человек должен перевезти волка, козу и капусту на другой берег реки. Для этого у него есть одна лодка, но она настолько мала, что он может каждый раз брать с собой только одну из трех вещей. Можно ли безопасно перевезти все три вещи на другой берег реки? Заметьте, что волк и коза или коза и капуста никогда не должны находиться на одной стороне реки без присмотра человека. По крайней мере, волк не вегетарианец и не любит есть капусту.

Мы строим граф для этой задачи, где каждое допустимое состояние представлено вершиной в графе, и ищем кратчайший путь в этом графе. Итак, пусть S = {M, W, G, C}, где M, W, G, C — человек, волк, коза и капуста. Состоянием для этой задачи является пара (X, Y ), где {X, Y } — разбиение S. Элементы в X все еще находятся на начальном берегу реки, а элементы в Y уже на другом берегу. Государство является правовым государством, если W,G ∈ X, Y ⇒ M ∈ X, Y и G, C ∈ X, Y ⇒ M ∈ X, Y, вы не можете оставить в покое капусту и волка или козу и капуста без присмотра. Теперь построим граф G = (V, E), который имеет вершину для каждого допустимого состояния этой задачи. У нас есть направленное ребро (v1 , v2 ) ∈ E, если мы можем попасть из состояния v1 = (X1 , Y1 ) в состояние v2 = (X2 , Y2 ) всего за одну поездку на лодке через реку. Все ребра получают вес ce = 1. Теперь задачу можно решить, вычислив кратчайший путь из состояния (вершины) s = (S, 😉 в состояние (вершину) t = (;, S). Получим 7 как решение для кратчайшего пути.

Упражнение 7

Рассмотрим следующую модификацию алгоритма Дейкстры для работы с отрицательными весами: Определить наименьший вес c в ℤ во взвешенном графе G = (V,E,w), т. е. ребро e st w(e) = c. Тогда для всех ребер f в E положим w'(f) := w(f) – c. Тогда G'=(V,E,w') не имеет отрицательных весов. Корректно ли работает эта версия алгоритма на этом типе графа? Докажите свое утверждение.

Теперь мы утверждаем, что DJP не работает правильно на G', потому что эта модификация не поддерживает свойство кратчайшего пути, т. е. (-c) — положительное число, поэтому вы добавляете его n раз для n-пути. Следующий контрпример доказывает это:

исправлены упражнения на задачи кратчайшего пути

Делиться
ru_RURU