Некоторые задачи оптимизации, которые можно решать с помощью графовых алгоритмов:

• Задача коммивояжёра. 1 Требуется посетить все вершины графа и вернуться в исходную вершину, минимизировав затраты на проезд или время. 1 Например, составить наиболее выгодный маршрут доставки деталей рабочим цеха или хлеба с хлебозавода по заданному числу булочных и других торговых точек. 1
• Задача о кратчайшем пути. 1 Как кратчайшим путём попасть из одной вершины графа в другую? 1 Например, как с наименьшим расходом топлива и времени попасть из пункта А в пункт Б. 1
• Задача о максимальном потоке. 1 Как послать максимально возможное количество грузов из начального пункта в конечный пункт, если пропускная способность путей между пунктами ограничена? 1
• Оптимизация маршрутов. 2 Чтобы построить маршрут, можно представить пункты назначения в виде вершин графа, а рёбрами станет расчётное время, за которое водитель перемещается между пунктами. 2 Таким образом, с помощью алгоритмов поиска путей возможно найти оптимальные варианты маршрутов. 2