Путь из начальной вершины xН к конечной вершине xК - последовательность дуг, начинающаяся в вершине xН Î Х, заканчивающаяся в вершине xК ÎХ, и такая, что конец очередной дуги является началом следующей (i - номер пути): (xН, xi1)(xi1, xi2)…(xil-1, xil)(xil, xК).
Элементарный путь – путь, в котором вершины не повторяются.
Простой путь – путь, в котором дуги не повторяются.
Маршрут - последовательность рёбер, составляющих, как и путь, цепочку.
Длина пути взвешенного графа определяется как сумма весов его дуг. Если граф не взвешен, то можно считать веса всех дуг равными 1, и
тогда длина пути - это количество дуг, составляющих путь.
Кратчайшим путем между выделенной парой вершин xН и xК называется путь, имеющий наименьшую длину среди всех возможных путей между этими вершинами.
При построении длиннейшего пути рассматриваются элементарные или простые длиннейшие пути, длиннейшие пути с заданным числом выполненных циклов. Длиннейший путь между xН и xК - путь, имеющий наибольшую длину среди всех возможных путей между этими вершинами.