Кратчайшие пути

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

Пути с минимальным количеством промежуточных вершин

Задача: найти путь между двумя заданными вершинами графа (орграфа), количество промежуточных вершин (и, соответственно, ребер) в котором минимально.

Для решения данной задачи существует эффективный алгоритм, имеющий линейную сложность как по числу вершин, так и по числу ребер - волновой алгоритм (другие названия - поиск в ширину, алгоритм степного пожара).

Пример прикладной задачи: необходимо добраться на самолете из города A в город B при условии, что между ними нет прямого авиационного сообщения, совершив при этом минимальное количество перелетов (при условии, что заданы возможные промежуточные аэропорты, и для каждой пары аэропортов известно, существует ли между ними прямой маршрут).

Решение: построим граф (орграф - если бывают "несимметричные" маршруты), вершины которого соответствуют всем возможным аэропортам, а ребра (дуги) - прямым маршрутам между ними. Задача сводится к нахождению маршрута с минимальным количеством промежуточных вершин между вершинами, соответствующими A и B.