Какой самый быстрый алгоритм поиска кратчайшего и дешевого пути на поезде из одной точки в другую

Самый быстрый способ - это посмотреть ключевые станции маршрута через Google map. Для вашего маршрута ключевыми станциями являются Рязань и Грязи.
Вариант: Поезд Челябинск -Москва Казанская 391У. Посадка на Ульяновск-Центр. в 20:07. Сидячий билет в вагон 14 - 895 рублей. Выходим в Рязань-1 в 7:42. перемещаемся по городу (пешком, троллейбус, такси и т. д.) на вокзал Рязань-2 (в запасе около 3-х часов - можно пешком пол-Рязани обойти). Садимся на скоростной двухэтажный поезд 740Ж "Москва Казанская - Воронеж" в 10:34 и едем в Грязи Воронежские в сидячем вагоне за 667 рублей. В 13:22 выходим в Грязи Воронежские, проходим подземный тоннель направо - садимся в маршрутку №507 за 40 рублей и едем в Липецк. В 14:00 вы в Липецке.

Итог: цена 895+667+50= 1612 рублей
Время в пути: 18 часов.
Возьмите с собой покушать и несколько пакетиков с чаем. Кипяток в термопоте есть.

Скажите, откуда и куда едете, подскажем, как добраться. Кстати, кратчайший путь не обязательно самый дешёвый.

Без "посмотри там то" и "гугл тебе в помощь", к сожалению, не получится. Т. к. даже для того, ходят ли поезда из одной точки в другую, уже придется смотреть в интернете расписание. Вы же не на вокзал поедете за этим?
И кратчайший путь - не значит дешевый путь.

Я честно скажу что не силён в теории графов, но как мне видится данная задача представляет из себя классический поиск кратчайшего пути в графе. Если я не ошибаюсь, то универсального алгоритма который давал бы наибольшую производительность нет, быстрота алгоритма во много определяется свойствами графа. На практике как мне кажется чаще всего используют алгоритм А*: https://ru.wikipedia.org/wiki/A*