Необходимо придумать транспортную схему, и найти маршрут движения автоколонны минимальной длины используя метод Белмана.

Пример 1:

Необходимо придумать транспортную  схему, и найти маршрут движения автоколонны минимальной длины используя метод Белмана.

Колонна автомашин должна доставить груз из пункта A в пункт B . Дорожная сеть представлена на рис.1.

Рис.1.

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

Решение от преподавателя:

Возле каждой дуги проставлена длина соответствующего отрезка маршрута. Требуется найти маршрут движения автоколонны минимальной длины. Прежде всего, разобьём вершины на уровни. Нулевой уровень: вершина A ; первый уровень: вершины 1, 2, 3; второй уровень: вершины 4, 5, 6; третий уровень: вершины 7, 8, 9; четвёртый уровень: вершина B , имеющая номер 10. Тем самым получаем следующие этапы.

1-й этап. Рассматриваются вершины 3-го уровня. Именно из этих вершин можно попасть в вершину по пути, содержащему ровно одно ребро. Внесём информацию в таблицу.