Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Задача о кратчайшем пути между двумя пунктами.




Известна схема дорог. Требуется перевезти груз из одного пункта в другой по маршруту минимальной длины.

Пример: Найдем маршрут минимальной длины от пункта 1 к пункту 11.

Припишем вершинам числа вместо номеров. Для 11-й вершины это 0.

11-я вершина соединена с 8-й, 9-й и 10-й вершинами, которым припишем числа 0+5=5, 0+5=5, 0+4=4 соответственно. Все эти ребра покажем двумя чертами со стрелками.

По числам 8-й и 9-й вершин найдем число 5-й вершины: min(5+7, 5+8)=12. Ребро (5,8) изобразим двумя чертами со стрелкой.

По числам 9-й и 10-й вершин найдем число 6-й вершины: min(5+7, 4+3)=7. Ребро (6,10) изобразим двумя чертами со стрелкой.

По числам 9-й и 10-й вершин найдем число 7-й вершины: min(5+4, 4+6)=9. Ребро (7,9) изобразим двумя чертами со стрелкой.

По числу 5-й вершины определим число 2-й вершины: 12+7=19. Ребро (2,5) изобразим двумя чертами со стрелкой.

По числам 5-й, 6-й и 7-й вершин определим число 3-й вершины: min(12+2, 9+2, 7+6)=11. Ребро (3,7) изобразим двумя чертами со стрелкой.

По числам 6-й и 7-й вершин найдем число 4-й вершины: min(7+3, 9+8)=10. Ребро (4,6) изобразим двумя чертами со стрелкой.

По числам 2-й, 3-й и 7-й вершин определим число 1-й вершины: min(19+1, 11+5, 10+4)=14. Ребро (1,4) изобразим двумя чертами со стрелкой. Длина кратчайшего пути равна 14.

Двигаемся из начальной вершины 1 в конечную вершину 11 по ребрам со стрелкой. Получаем кратчайший путь 1-4-6-10-11. Его длина равна 14.

 

Задача.

  1. Найти маршрут минимальной длины от пункта 1 к пункту 10.

 






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных