Нахождение кратчайшего маршрута в графе с помощью алгоритма Дейкстры

Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.
Нахождение кратчайшего пути – жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet и т.п.
Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.
Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути:
алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами);
алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин);
алгоритм Йена (для нахождения k-оптимальных маршрутов между двумя вершинами).