алгоритм поиска кратчайшего пути в графе
Важно
учитывается длинна пройденного ребра — вес
Задача
стартовая точка A
конечная точка G
A—B—F—G
| / |
| / |
| / |
| D |
| / |
| / |
|/ |
C——E
составляется таблица, на котором на первом этапе записываются значения тех вершин, в которые мы можем попасть из стартовой точки. Все остальные вершины являются не достижимыми и мы их помечаем знаком бесконечности.
На втором этапе мы помечаем эти (B и C) вершины как рассмотренные,
На третьем этапе мы рассматриваем вершины, на которые мы можем попасть из точек B и C и в таблице записываем значения из точки A до точек, которые мы достигаем из вершин B и С. Опять же помечаем эти точки, как уже рассмотренные.
На следующем этапе мы достигаем конечной точки G, но у нас происходит перерасчет (мы находим путь до F, до которого оказывается короче и перезаписываем значение в таблице).
И на следующем этапе мы проделываем тоже самое и находим самый оптимальный путь и узнаем, что из точки A в точку G мы можем добраться за пять условных единиц.