- Оптимальный путь — это путь с самой минимальной суммой рёбер между двумя точками (вершинами) на графе.
- Истоком называется вершина графа, в которую нет входящих рёбер. Стоком называется вершина графа, для которой нет исходящих рёбер.
- Оптимальный путь получил применение в GPS-навигаторах. В качестве вершин выступают перекрёстки, а дороги являются рёбрами, которые лежат между ними. Поиск оптимального пути используется также в системах искусственного интеллекта, в компьютерных играх.
- Пример. Найдём с помощью графа кратчайший путь из пункта А в пункт В.
Решение. Необходимо построить весовую матрицу и с её помощью дерево перебора.
Ответ. Кратчайший путь — ADEB с весом 3.
