Вес и длина пути

Иногда дугам графа G приписываются числа- дуге (x_i x_j) ставится в соответствие некоторое число C_ij, называемое весом или длиной дуги.

В этом случае граф G называется графом со взвешенными дугами.

Если веса (числа v_j) приписываются вершинам x_j, то такой граф называется графом со взвешенными вершинами, а сами числа v_j – весами вершин.

Если в графе веса приписаны и дугам и вершинам, то такой граф называется просто взвешенным.

При рассмотрении пути μ, представленного последовательностью дуг а₁ , а₂, …., а_q за его вес принимается число l (μ), равное сумме весов всех дуг, входящих в этот путь, причем каждая дуга считается столько раз, сколько она встречается в данном пути.

Длиной пути μ называется количество дуг, входящих в него, причем каждая дуга считается столько раз, сколько она входит в этот путь.