Вага ребра – значення, поставлене у відповідність до цього ребра зваженого графа. Зазвичай вага – речове число, в такому випадку його можна інтерпретувати як «довжину» ребра. Зважений граф – граф, кожному ребру якого поставлено у відповідність певне значення (вага ребра).
