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