От поиска кратчайших пересадок к поиску самых дешёвых маршрутов. Как жадный, но умный алгоритм строит идеальный путь в мире, где у каждой дороги — своя цена. От карты поездов до логистики доставки. В прошлый раз мы вооружились поиском в ширину (BFS) и научились находить кратчайший путь по количеству шагов. Это сработает, если вы ищете друга в соцсети (где все связи равны) или хотите попасть из одного конца метро в другой с минимальным числом пересадок. Но жизнь редко бывает такой простой. В реальности у каждого пути есть своя цена: километры, время, деньги, расход бензина. Прямая дорога через горный перевал может быть короче по карте, но дольше и опаснее, чем объезд по равнине. Маршрут с одной пересадкой может стоить дороже, чем с двумя, но на более дешёвых видах транспорта. Как найти не путь с минимальным числом отрезков, а путь с минимальной суммарной стоимостью? Эту задачу блестяще решает алгоритм Дейкстры. Это логичное и мощное развитие темы графов: переход от невзвешенных графов (
Публикация доступна с подпиской
Базовый