Взвешенный граф — это граф, в котором каждому ребру назначено некоторое числовое значение (вес ребра). 14 Это может быть расстояние, время, стоимость, мощность или другая характеристика, связанная с соединением вершин. 4

От обычного графа взвешенный отличается тем, что характеризуется числовым значением для более точного конструирования схемы. 3 Невзвешенный граф не присваивает вес рёбрам, а лишь отражает факт наличия связи. 3

Пример взвешенного графа — транспортная сеть, в которой рёбрам присвоены весы: они показывают стоимость перевозки груза по ребру и пропускные способности дуг. 1

Обычные графы тоже возможно представить в виде взвешенных, если считать, что все их рёбра обладают весом равным единице. 2