Рубрика: Графы

не важно

длительный этот путь или нет, а самое

главное

количество пройденных участков или существует ли путь

ЗАДАЧА

Найти путь из точки A в точку B за минимальное количество шагов

Процесс решения

задаём для каждой вершины название
создаём объект, который содержит вершины (содержит путь к точке B)

используется Cтруктура Данных «очередь»

• состоит из каких то элементов
• элементы всегда добавляются в конец структуры, а извлекаются из её начала
• тот кто пришел на кассу первым — уходит первым
• тот кто пришел на кассу последним — уходит последним
• FIFO — FIRST IN FIRST OUT

алгоритм поиска кратчайшего пути в графе

Важно

учитывается длинна пройденного ребра — вес

Задача

стартовая точка A
конечная точка G

A—B—F—G
|       / |
|      /  |
|     /   |
|    D  |
|   /     |
|  /      |
|/        |
C——E

составляется таблица, на котором на первом этапе записываются значения тех вершин, в которые мы можем попасть из стартовой точки. Все остальные вершины являются не достижимыми и мы их помечаем знаком бесконечности.

На втором этапе мы помечаем эти (B и C) вершины как рассмотренные,

На третьем этапе мы рассматриваем вершины, на которые мы можем попасть из точек B и C и в таблице записываем значения из точки A до точек, которые мы достигаем из вершин B и С. Опять же помечаем эти точки, как уже рассмотренные.

На следующем этапе мы достигаем конечной точки G, но у нас происходит перерасчет (мы находим путь до F, до которого оказывается короче и перезаписываем значение в таблице).

И на следующем этапе мы проделываем тоже самое и находим самый оптимальный путь и узнаем, что из точки A в точку G мы можем добраться за пять условных единиц.