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

Например, в алгоритме поиска в ширину (BFS) требуется найти путь от одной вершины графа до другой, причём путь должен быть минимальным по количеству рёбер. 35 Если длины рёбер графа равны между собой, BFS является оптимальным, то есть всегда находит кратчайший путь. 4 В случае взвешенного графа BFS находит путь, содержащий минимальное количество рёбер, но не обязательно кратчайший. 4

Также нахождение пути с минимальным количеством рёбер важно в задачах искусственного интеллекта, связанных с поиском решения с минимальным количеством ходов. 5 В таком случае состояния «умной машины» представляются как вершины, а переходы между ними — как рёбра. 5