Задачата за намиране на най-къси пътища в ориентирани
тегловни графи: за какви пътища става дума и как се
дефинира тегло на път.  Отрицателни цикли -- дефиниция
и проблеми при наличието на отрицателни цикли.
Как се дефинира теглото на най-къс път \delta(u,v).

Варианти на задачата за най-къс път.

Теорема 99: най-къс път се състои от най-къси подпътища.

Дърво на най-късите пътища.

Ключови разлики между задачата за намиране на МПД
и задачата за намиране на най-къс път.

Алгоритмични примитиви ISS и RELAX.  Свойства:

  -- Лема 41: неравенство на триъгълника
  -- Лема 42: ако графът е инициализиран с ISS, слес произволна
              серия от изпълнения на RELAX, v.d е горна граница за \delta(s,v), а ако
              веднъж се достигне равенство, то вече не се променя
  
  -- Лема 43: ако няма път от s до v, то след произволна серия от изпълнения на RELAX,
              v.d е безкрайност
  -- Лема 44: конвергенция

Алгоритъм на Дийкстра (Алгоритъм 34) с псевдокод.  Какви са теглата?  Доказателство за коректност
на алгоритъма на Дийкстра (Теорема 100).  Сложност по време на
алгоритъма на Дийкстра.

Теорема 101: алгоритъмът на Дийкстра слага върховете в дървото
в реда на теглата.

Алгоритъм за намиране на най-къси пътища в тегловни дагове (Алгоритъм 35)
с псевдокод.  Какви са теглата?  Анализ на коректност и сложност.  Предимства на този алгоритъм
над алгоритъма на Дийкстра.

Алгоритъм на Bellman-Ford за намиране на най-къси пътища (Алгоритъм 36) с псевдокод.
Какви са теглата?  Анализ на коректност и сложност.