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

Алгоритм еще не получил официального наименования, пока что его называют KLOS по фамилиям разработчиков: Джонатан Келнер, Инь Тат Ли, Лоренцо Орекиа и Аарон Сидфорд.

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

Как отмечают исследователи, пока разработана лишь теоретическая основа алгоритма, а на его реализацию может уйти еще некоторое время.