Определение 10.

Взвешенным графом или орграфом называется такой граф (или орграф), каждому ребру которого приписано число, называемое весом ребра.

При формальном описании вес ребра будет дополнительным элементом неупорядоченной или упорядоченной пары вершин, образуя вместе с этой парой, так называемый, «триплет».

Например, рассмотрим пару вершин С и D в ориентированном графе на рисунке 9. Припишем ребру СD некий вес и в результате получим триплет

.

При проходе по ориентированному графу вес ребра считается ценой этого прохода.