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

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

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

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