251
правка
Изменения
м
Дано{{Задача|definition = Дана сеть автомобильных дорог:* ориентированный граф <tex>G=(V,E)</tex>, где** <tex>V</tex> — множество перекрёстков,** <tex>E</tex> — множество дорог;* <tex>l(u,v) \geqslant 0</tex>— среднее время, которое занимает проезд по дороге,* <tex>|V|=n, |E|=m</tex>,
Мы будем рассматривать сеть автомобильных дорог:* <tex>V</tex> — множество перекрёстков* <tex>E</tex> — множество дорог* <tex>l(u,v)</tex> — среднее время, которое занимает проезд по дороге}}
→Проблема поиска кратчайшего пути
== Проблема поиска кратчайшего пути ==
* отправная точка — вершина <tex>s</tex>, пункт назначения — вершина <tex>t</tex>
Цель: найти кратчайший путь <tex> s \rightsquigarrow t</tex>
==Алгоритм Дейкстры==
