ТОР 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.
Задача.
Не нашли, что искали? Воспользуйтесь поиском:
|