Алгоритм Дейкстры и физика

[MaximChistov]

А что будет, если мы будем искать ближайшую вершину к началу при помощи SleepSort? Можно представить это так: пустим «воду, разливающуюся по графу» такую, что она проходит ребро за время пропорциональное его весу. «Разливать» ее будем от множества A. Тогда время от «пуска воды» до достижения некоторой вершины (из множества сортируемых вершин, а только их она и может достигнуть) будет как раз суммой времени достижения предыдущей и времени прохода ребра — это и есть та характеристика, по которой мы хотим сортировать вершины на шаге алгоритма Дейкстры (это SleepSort: «вода дошла» это и есть «sleep (prev + edge); вода дойди;»).

Классический волновой алгоритм :) Для него причем вес графов добавляется легко — за проход по клеткам с весом N прибавляется N очков, где чем меньше N тем лучше проходимость.

[masai]

Строго говоря, разряд не «ищет» путь, он просто идёт по нему. Чтобы понять, почему там не Дейкстра, достаточно вспомнить, почему ток идёт по пути наименьшего сопротивления.

[sply]

Ток идет по всем путям. По пути наименьшего сопротивления идет наибольший ток.