ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ (SHORTEST ROUTE PROBLEM)

задача о нахождении на ориентированном графе пути наименьшей длины между двумя заданными его вершинами. Длиной пути такого графа называется сумма длин дуг, составляющих этот путь. 3. о к.п. возникает чаще всего при решении трансп. задач, дискретных задач программирования дин. и др. В задачах сетевых методов планирования и управления алгоритмы решения 3. о к.п. используют для нахождения критического пути. Известно несколько эффективных методов ее решения. Так, для анализа трансп. сетей применяют алгоритм, основанный на методе последовательного анализа вариантов. См. Программирование матем.