Главная > Энциклопедия кибернетики. Т.1
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
След.
Макеты страниц

Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

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

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

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

Н. З. Щор

1
Оглавление
email@scask.ru