Кожній дузі (i, j) мережі поставлена у відповідність її довжина
, або тривалість проходження одиниці транспортного потоку, що у загальному випадку може бути позитивним і негативним числом.
У ряді відомих алгоритмів робиться додаткове припущення про те, що G (V, Е) не містить циклів негативної довжини.
Очевидно, що якщо в джерело помістити одиницю потоку, а в стік одиничний попит, пропускні спроможності всіх дуг вважати безкінечними і відшукувати припустимий потік мінімальної вартості (за умови, що lij - вартість переміщення потоку), те, розв'язавши задачу про потік мінімальної вартості, знайдемо найкоротший шлях прямування цієї одиниці.
Проте у розрахунковому відношенні більш ефективними виявилися спеціальні, так називані комбінаторні алгоритми, аналізовані в даному розділі. У цих алгоритмах вихідні дані подані у виді списків дуг, тобто для кожної вершини дається список тих дуг (i, j), що інцидентні їй, разом із їхніми довжинами
. Оцінки числа операцій алгоритмів приведені в табл. 3.Спочатку роздивимося основні алгоритми рішення задачі пошуку найкоротшого шляху між двома вершинами: 1 (джерело) і п (стік).
Таблиця 3 - Оцінки числа операцій алгоритмів
Метод Белмана. Скористаємося рівнянням Белмана для визначення найкоротшого шляху між вершинами 1 і n. Визначимо
- довжину найкоротшого шляху з вихідної вершини 1 у вершину j за умови, що вершини пронумеровані числами 1, 2, 3,..., п. Шлях найкоротшої довжини знаходиться з такого рівняння:
j=2,3,…,n;u
j=0
У результаті розрахунків знаходиться (якщо воно існує) дерево найкоротших відстаней із коренем у вершині 1, у якому довжина єдиного шляху з 1 у j дорівнює uj, j=2, 3,..., п.
Алгоритми Дийкстра. Роздивимося мережу G (V, Е), у котрої довжини lijусіх дуг позитивні. Тоді відомий алгоритм Дийкстра може бути записаний у такий спосіб.
Крок 0. Покласти
S={1,2,3…,n}
Крок 1. Знайти
, для котрого = 
, якщо uk =+ 
- стіп; не існує шляху у вершини, що залишилася в S. Положимо S = S - {k}. Якщо S = 
- стіп; обчислення закінчені.Крок 2. Покласти
= min{ 
} для всіх (k, j) 
Е. Перейти до кроку 1.При раціональному засобі організації обчислень алгоритм оцінюється в 0 (т 1оg п) операцій. Зауважимо, що для мережі G (V, Е), що є плоским графом, алгоритм обчислення найкоротших шляхів із 1 у всі інші вершини потребує 0 (п 1оg п) операцій.
Якщо припустити, що мережа G (V, Е) є ациклічний тобто не містить циклів, то в ній можна пронумерувати вершини так, що для кожної дуги з i у j виконується умова i < j. Очевидно, таке упорядкування може бути виконане за 0 (т) операцій. Тоді для приклада рівняння Белмана можуть бути вирішені простим обчисленням: и1 = 0, и2 залежить тільки від и1, и3 залежить від и1, и2, иj залежить від и1, и2,..., иj-1 і т.д. Таким чином, рішення може бути отримане за 0 (т) операцій.
Метод Белмана - Форда. Роздивимося мережу G (V, Е), у котрої або відсутні цикли, або довжини дуг ненегативні. Метод послідовних наближень, запропонований Белманом і Фордом, складається в такому.
Нехай uj(k) - довжина найкоротшого шляху від вихідної вершини до вершини j за умови, що шлях містить не більш ніж k дуг. Спочатку положимо
Тоді
та 
. Для дуг k = 2, 3,...,n- 1 необхідно 0 (n) ітерацій. Кожна ітерація потребує 0 (m) операцій. Отже, метод потребує 0 (т п) операцій. Зауважимо, що для плоских графів потрібно 0 ( 
) операцій.Він [17] запропонував модифікацію цього методу, що скорочує загальне число додавань і порівнянь приблизно в чотирьох разу у випадку повної мережі й у два рази в довільному випадку.
Задача визначення найкоротших шляхів між усіма парами вершин. Більш загальною задачею про пошук найкоротших шляхів є задача визначення найкоротших маршрутів або шляхів якнайшвидшої доставки вантажів між усіма парами вузлів транспортної мережі.
Не розглядаючи кожний з алгоритмів пошуку найкоротших шляхів, приведених у табл. 3, опишемо ідеї їхньої побудови.
Будемо шукати найкоротші шляхи між вершинами в мережі з позитивними і негативними довжинами дуг, починаючи з вершини 1. Очевидно, буде потрібно 0 (тп) обчислень для того, щоб знайти найкоротші шляхи з вершини 1 у всі інші вершини. Замінимо довжину кожної дуги
на 
. Довжина шляху з i у j, визначена за значеннями 
, відрізняється від щирої довжини на константу 
. Отже, рішення задачі визначення всіх найкоротших пар шляхів із довжинами є рішенням вихідної задачі. Оскільки тепер усі довжини дуг невід’ємних, можна застосувати метод Дийкстра для кожній з останніх п - 1 задач. У результаті вся задача буде вирішена за 0 ( 
) операцій, а для плоского графа за 0 ( 
) операцій. У [18] запропонований алгоритм для невід’ємних дуг мережі G (V, Е), у якому очікуване число обчислень дорівнює 0 ( 
).Нехай мережа G (V, Е) складається з неорієнтованих дуг і ми хочемо знайти найкоротший шлях між двома визначеними вершинами. Якщо всі довжини дуг невід’ємних, те можна замінити кожну неорієнтованих дугу парою симетричних орієнтованих дуг (i,j) і (j, i) із
і застосувати будь-який із зазначених вище алгоритмів.Проте якщо довжина дуги (i,j) негативний, те цей підхід нездатний, тому що в мережі з'явиться негативний цикл (i,j), (j, i)
У загальному випадку можна скористатися, наприклад, методом Белмана- Форда для визначення існування циклу негативної довжини в G (V, Е). Якщо мережа є сильнозв`язною, то цикл негативної довжини існує тоді і тільки тоді, коли uj(n) < uj(n-1) для деякої вершини j. Мережа може бути перевірена на існування негативного циклу за 0 (тп) операцій.
У розглянутих вище задачах передбачалося, що однорідний транспортний потік, що виходить із дуги (i, j)
Е, дорівнює потокові, що входить у цю дугу. Проте в ряді практичних ситуацій це припущення не виконується. Наприклад, при транспортуванні вантажів може відбуватися їхнє псування або втрата (наприклад, вивітрювання), що призводить до зменшення потоку під час його переміщення по дузі (i, j) транспортної мережі G (V, Е).Тому для рішення подібних задач необхідно відмовитися від припущення, відповідно до якого при проходженні по дугах мережі G (V, Е) потік залишається незмінним, і припустити, що кількість однорідного потоку, що проходить по дузі, може збільшуватися або зменшуватися.
Будемо вважати, що якщо в будь-яку дугу (i, j)
Е з вершини i виходить 
одиниць потоку, то з цієї дуги у вершину j увійде 
одиниць потоку. Розмір 
має назву коефіцієнта підсилення або просто посиленням дуги (i, j).Якщо
> 1, то потік по дузі (i, j) посилюється. Якщо = 1, то потік по дузі (i, j) залишається незмінним. Якщо 0 < < 1, то потік по дузі (i, j) скорочується (частково поглинається). Якщо = 0, то потік по дузі (i, j) губиться (поглинається цілком) і дана дуга звичайно розглядається як стік. Якщо < 0, то для кожної одиниці потоку, що входить у вершину i, повинно потрапити одиниць потоку у вершину j, тобто в даному випадку дуга (i, j) може розглядатися яка влаштувала попит на потік.