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

• Поиск в ширину. 1 Систематически обходит все рёбра графа для «открытия» всех вершин, достижимых из выделенной начальной вершины. 1 В процессе обхода строится дерево поиска в ширину с корнем в начальной вершине, содержащее все достижимые вершины. 1
• Поиск в глубину. 4 Рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных. 4 Осуществляет поиск вглубь графа, а также использует стек, чтобы не забыть «получить» следующую вершину для начала поиска, когда на любой итерации возникает тупик. 4

Для решения задачи о кратчайшем пути используются, например, следующие алгоритмы: 23

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