Алгоритмы нахождения оптимального пути

Путь из начальной вершины x_Н к конечной вершине x_К - последовательность дуг, начинающаяся в вершине x_Н Î Х, заканчивающаяся в вершине x_К ÎХ, и такая, что конец очередной дуги является началом следующей (i - номер пути): (x_Н, x_i1)(x_i1, x_i2)…(x_il-1, x_il)(x_il, x_К).

Элементарный путь – путь, в котором вершины не повторяются.

Простой путь – путь, в котором дуги не повторяются.

Маршрут - последовательность рёбер, составляющих, как и путь, цепочку.

Длина пути взвешенного графа определяется как сумма весов его дуг. Если граф не взвешен, то можно считать веса всех дуг равными 1, и

тогда длина пути - это количество дуг, составляющих путь.

Кратчайшим путем между выделенной парой вершин x_Н и x_К называется путь, имеющий наименьшую длину среди всех возможных путей между этими вершинами.

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