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

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

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

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

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

Тогда

,

где .

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

.

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

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

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

Граф или орграф, в котором вершины и ребра имеют некоторые количественные характеристики, называются сетью.

И, наконец, дадим определение связного графа и цикла на графе.