Определение 11

Пример.

Стоимость перевозки по заданному сегменту (ребру) воздушной линии;

стоимость проезда по заданному отрезку платной автомагистрали и т.п.

В общем случае весом ребра в транспортных сетях может служить любой параметр, определяющий техническую оснащенность данного ребра сети: высота эшелона воздушной линии, ширина и число разрешенных полос движении на отрезке дорожной сети, пропускная способность трубопровода, разрешенная скорость движения и т.д.

Стоимость пути по взвешенному графу равна сумме весов всех ребер пути.

Кратчайший путь во взвешенном графе – это путь с минимальным весом, даже если число ребер в пути можно и уменьшить (Рисунок 10).

Рисунок 10. Кратчайший путь во взвешенном графе: Р₁=24усл.ед., Р₂=36усл.ед.

Введем следующие обозначения для длины пути Р на графе.

Обозначим через – длину пути из вершины А в вершину В,

тогда

,

где .

Длина кратчайшего пути на графе принимает обозначение

.

Здесь – множество альтернативных путей из А в В.

Далее введем определение сети.