ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ

ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ - Задача о нахождении на ориентированном графе пути наименьшей длины между двумя заданными его вершинами.(Родников А.Н. Логистика: Терминол. слов.-М., 1995) Длиной пути такого графа называется сумма длин дуг, составляющих этот путь. Задача о кратчайшем пути возникает чаще всего при решении транспортных задач, дискретных задач динамического программирования и др. В задачах сетевых методов планирования и управления алгоритмы решения задачи о кратчайшем пути используют для нахождения критического пути. Известно несколько эффективных методов ее решения. Так, для анализа транспортных сетей применяют алгоритм, основанный на методе последовательного анализа вариантов.(Родников А.Н. Логистика: Терминол. слов.-М., 1995) См. также: Программирование математическое °