2015-02-04
1656
Задача состоит в том, чтобы найти кратчайший путь на графе от какой-то выделенной вершины до любой другой вершины.
Задачи определения кратчайшего пути можно решить с использованием метода присвоения меток, когда каждому узлу присваивается метка из двух чисел.
Первое число – минимальное расстояние от стартового узла до данного узла.
Второе число – номер предыдущего узла на пути от стартового узла к данному узлу.
Узел, для которого определяется путь от стартового узла, назовем помеченным.
Узел, для которого такой путь еще не определен, назовем непомеченным.
Если определено кратчайшее расстояние от стартового узла до данного узла, то соответствующую метку назовем постоянной и будем обозначать в круглых скобках.
Все остальные метки – временные и обозначаются в квадратных скобках.
Узлы с постоянными метками будем закрашивать.
Пример 1: Узел 7 – склад, остальные узлы – строительные площадки компании. Показатели на дугах – расстояния в километрах. Надо найти кратчайшие расстояния от склада до строительной площадки. Какова длина кратчайшего пути от склада до строительной площадки? Проходит ли кратчайший путь от склада к строительной площадке 1 через строительную площадку 2? Какова длина кратчайшего пути от склада до строительной площадки 2? Проходит ли кратчайший путь от склада к строительной площадке 2 через строительную площадку 4?
|
|
|
