Розділ III.Пошук маршруту у графі

Зважені графи

У реальних задачах на графах часто потрібно брати до уваги додаткову інформацію — відстань між окремими пунктами, вартість проїзду, час проїзду тощо. Для цього використовують поняття зваженого графа.

Зваженим називають граф, кожному ребру e якого приписано дійсне число w (e). Це число називають вагою ребраe. Аналогічно означають зваженийорієнтований граф: це такий орієнтований граф, кожній дузіeякого приписане дійсне числоw (e), яке називаєтьсявагою дуги.

Розглянемо два способи зберігання зваженого графа G = (V, E) в пам' яті комп' ютера.

Нехай |V| = n, |E| = m.

Перший — подання графу матрицею ваг W, яка являє собою аналог матриці суміжності. Її елемент wij = w (vi, vj), якщо ребро або дуга (vi, vj) ОE. Якщо ж ребро або дуга (vi, vj) ПE, то wij= 0чи wij=Ґзалежно від розв’язуваної задачі.

Другий спосіб — поданням графу списком ребер. Для зваженого графу під кожний елемент списку E можна відвести три комірки — дві для ребра й одну для його ваги, тобто всього потрібно 3m комірок.

Довжиною шляху в зваженому графі називають суму ваг ребер

(дуг), які утворюють цей шлях. Якщо граф не зважений, то вагу кожного ребра (кожної дуги) уважають рівною одиниці та отримають раніше введене поняття довжини шляху як кількості ребер (дуг) у ньому.