Навантажений граф - орграф G = (V, X), для якого задана функція ставить у відповідність кожній дузі цього графа деякий дійсне число - довжина (вага) дуги x l (x). Можна задати за допомогою матриці ваг:
Замкнуте шлях - шлях (маршрут), у якого перша і остання вершини збігаються. Замкнуте шлях, який проходить через кожну дугу (ребро) тільки 1 раз називається циклом. Цикл, який проходить через кожну вершину 1 раз називається простим.
Ланцюг - незамкнений шлях (маршрут), який проходить через кожну дугу (ребро) тільки 1 раз. Ланцюг, яка проходить через кожну вершину 1 раз називається простий.
Довжина шляху (для ненавантаженого графа) - кількість дуг, що входять в цей шлях.
Довжина шляху (для навантаженого графа) - сума ваг дуг, що входять в цей шлях. Мінімальний шлях [між вершинами v1 і vk] - шлях, який має мінімальну довжину серед всіх інших шляхів [з v1 у vk].
Алгоритм Дейкстри (поісл min шляху в навантаженому графі)
1. Покладемо l * (s) = 0 і будемо вважати цю мітку постійною. Для всіх v ОV, v № s, покладемо l * (v) = Ґ і будемо вважати ці мітки тимчасовими. Покладемо p = s.
2. Для всіх vОГp з тимчасовими мітками виконаємо: якщо l * (v)> l * (p) + l (p, v), то l * (v) = l * (p) + l (p, v) і Q (v) = р. Інакше l * (v) і Q (v) не змінювати, тобто l * (v) = min (l * (t), l * (p) + cpv). (Ідея полягає в наступному: нехай p - вершина, що одержала постійну мітку l * (p) на попередній ітерації. Переглядаємо всі вершини vОГp, що мають тимчасові мітки. Метка l * (v) вершини vОГp замінюється на l * (p) + l ( p, v), якщо виявляється, що її мітка l * (v)> l * (p) + l (p, v). У цьому випадку говоримо, що вершина v отримала свою мітку з вершини p, тому покладемо Q (v ) = p. За допомогою цих додаткових позначок будемо потім відновлювати сам шлях. Якщо l * (v) Ј l * (p) + cpv, то мітки залишаються колишніми.
3. Нехай V * - безліч вершин з тимчасовими мітками. Знайдемо вершину v * таку, що l * (v *) = min l * (v), v Про V *. Вважати мітку l * (v *) постійної для вершини v *.
4. Покладемо p = v *. Якщо p = t, то перейдемо до п.5 (l * (t) - довжина мінімального шляху). Інакше перейдемо до п.2.
5. Знайдемо мінімальний шлях з s в t, використовуючи мітки Q (v): П = s ... Q (t) t.