Как графы применяются в современных алгоритмах поиска кратчайших путей?

Графы применяются в современных алгоритмах поиска кратчайших путей для представления пространства, в котором происходит поиск. habr.com Вершины графа представляют собой точки или места, а рёбра графа — пути или дороги между этими точками. habr.com Веса на рёбрах графа могут представлять расстояния или стоимости перемещения между вершинами. habr.com

Некоторые алгоритмы поиска кратчайших путей на графах и их области применения:

• Алгоритм Дейкстры. ru.wikipedia.org tproger.ru Находит кратчайший путь от одной из вершин графа до всех остальных. ru.wikipedia.org Применяется в навигационных системах и картографии, в робототехнике, в системах бронирования и компьютерных сетях. tproger.ru
• Алгоритм Беллмана — Форда. ru.wikipedia.org Находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе. ru.wikipedia.org Вес рёбер может быть отрицательным. ru.wikipedia.org
• Алгоритм поиска A|*. ru.wikipedia.org Находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной). ru.wikipedia.org Применяется в задачах маршрутизации и навигации, особенно в играх и робототехнике. tproger.ru
• Алгоритм Флойда — Уоршелла. ru.wikipedia.org Находит кратчайшие пути между всеми вершинами взвешенного ориентированного графа. ru.wikipedia.org
• Алгоритм Джонсона. ru.wikipedia.org Находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. ru.wikipedia.org
• Алгоритм Ли (волновой алгоритм). ru.wikipedia.org Находит путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (рёбер). ru.wikipedia.org Применяется для трассировки электрических соединений на кристаллах микросхем и на печатных платах, а также для поиска кратчайшего расстояния на карте в стратегических играх. ru.wikipedia.org

Алгоритмы поиска кратчайших путей на графах используются в картографических сервисах, при построении пути GPS-навигатора, для представления и анализа дорожной сети и во многих других областях. is.ifmo.ru dspace.tltsu.ru