графі
Початкові поняття
Будемо розглядати орієнтовані графи G = дуг яких приписані ваги. Це означає, що кожній дузі? E поставлено у відповідність деяке дійсне число a (u, v), зване вагою даної дуги. p align="justify"> Нас цікавитиме знаходження найкоротшого шляху між фіксованими вершинами s, t? V. Довжину такого найкоротшого шляху ми будемо позначати d (s, t) і називати відстанню від s до t (відстань, визначену таким чином, може бути негативним). Якщо не існує жодного шляху з s в t, то вважаємо d (s, t) = +. Якщо кожен контур нашого графа має позитивну довжину, то найкоротший шлях буде завжди елементарним шляхом, тобто в послідовності v1, ..., vp НЕ буде повторів.
З іншого боку, якщо в графі існує контур негативною довжини, то відстань між деякими парами вершин стає невизначеним, тому що, обходячи цей контур достатню кількість раз, ми можемо показати шлях між цими вершинами з довжиною, меншою довільного дійсного числа. У такому випадку, можна було б говорити про довжину найкоротшого елементарного шляху, однак завдання, поставлене таким чином, ймовірно буде значно складнішим, так як, зокрема, вона містить у собі завдання існування гамільтонового шляху. p align="justify"> Можна дати багато практичних інтерпретацій задачі про найкоротших шляхах. Наприклад, вершини можуть відповідати містах, а кожна дуга - деякого шляху, довжина якого представлена ​​вагою дуги. Ми шукаємо потім найкоротші шляхи між містами. Вага дуги також може відповідати вартості (або часу) передачі інформації між вершинами. У такому випадку ми шукаємо найдешевший (або самий швидкий) шлях передачі інформації. Ще одну ситуацію отримуємо, коли вага дуги дорівнює ймовірності p (u, v) безаварійної роботи каналу передачі інформації. Якщо припустити, що аварії каналів не залежать одне від одного, то ймовірність справності шляхи передачі інформації дорівнює добутку ймовірностей складових його дуг. Задачу знаходження найбільш надійного шляху легко можна звести до задачі про найкоротший шлях, замінюючи ваги p (u, v) на a (u, v) = - lg p (u, v). p align="justify"> Спочатку розглянемо алгоритми знаходження відстані між вершинами, а не самих шляхів. Однак, знаючи відстань, ми можемо за умови позитивної довжини всіх контурів легко визначити найкоротші шляхи. Для цього достатньо зазначити, що для довільних s, t,? V (s, t) існує вершина v, така що d (s, t) = d (s, v) + a (v, t). p align="justify"> Дійсно, такою властивістю володіє передостання вершина довільного найкоротшого шляху з s в t. Далі ми можемо знайти вершину u, для якої d (s, v) = d (s, u) + a (u, v), і т.д.
З позитивності довжини всіх контурів легко випливає, що створена таким чином послідовність t, v, u, ... не містить повторень і закінчується вершиною s. Очевидно, що вона визначає (при зверненні черговості) найкоротший шлях з s в t. p align="justify"> Далі ми можемо знайти вершину u, для якої d (s, v) ...
