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

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

3. о к. п. возникает во многих приложениях, особенно при решении транспортных задач, дискретных задач программирования динамического и пр. В задачах сетевого планирования и управления алгоритмы решения 3. о к. п. используются для нахождения критического пути. Известно несколько эффективных методов решения 3. о к. п. Наиболее употребительны алгоритмы Минти, Веллмана — Шимбела и Форда. В СССР широкое применение для анализа транспортных сетей получил алгоритм, основанный на методе последовательного анализа вариантов, близкий к алгоритму Форда.

Н. З. Щор