Взвешенный граф
Граф, у которого вершины или рёбра характеризуются некоторой дополнительной информацией — весом вершин и/или рёбер.
Взвешенный граф — это граф, в котором каждое его ребро обозначается числовым значением, которое называется весом. Вес ребра представляет может представлять различные характеристики, такие как расстояние, время, стоимость или пропускная способность. Вес могут иметь не только рёбра графа, но и его вершины.