Иногда дугам графа G приписываются числа- дуге (xi xj) ставится в соответствие некоторое число Cij, называемое весом или длиной дуги.
В этом случае граф G называется графом со взвешенными дугами.
Если веса (числа vj) приписываются вершинам xj, то такой граф называется графом со взвешенными вершинами, а сами числа vj – весами вершин.
Если в графе веса приписаны и дугам и вершинам, то такой граф называется просто взвешенным.
При рассмотрении пути μ, представленного последовательностью дуг а1 , а2, …., аq за его вес принимается число l (μ), равное сумме весов всех дуг, входящих в этот путь, причем каждая дуга считается столько раз, сколько она встречается в данном пути.
Длиной пути μ называется количество дуг, входящих в него, причем каждая дуга считается столько раз, сколько она входит в этот путь.