Хочу поделиться знанием, которое не является секретом, в каких-то курсах по алгоритмам оно наверняка дается, но нагуглить его совсем не просто. Поэтому пусть будет.
Алгоритм Дейкстры можно обобщить на произовльную функцию длины пути, если только она удовлетворяет трем условиям:
Монотонность. При добавлении ребра к пути, его длина не уменьшается.
Консистентность. При добавлении одинакового ребра к путям одинаковой длины, получившиеся новые пути имеют одинаковую длину.
Оптимальность префикса. Если к двум путям приписать одинаковое ребро, то кратчайший путь останется кратчайшим.
Под катом я привожу доказательство корректности обобщенного алгоритма и показываю, как его применить в задаче на литкоде: Trapping rain water II.
Читать далее