Следующий класс задач, для нас не всегда безразлична цена перехода, от одного состояния к другому. Очень часто эта цена находиться наружи. Где там вы решаете задачи, где есть расстояния, там они есть. Любой путь от одной вершины к другой он выражается через расстояние. Появляется цена. Значит мы можем оценивать общую цену, во-первых пройденного пути для промежуточных точек, путей для маршрутов, которые вообще можно построить на графе. Вот если у меня на графе 15 маршрутов от начала до конца, меня и этих 15 интересуют только те, у которых путь оптимальный. Меньше или больше вопрос второй. Если усложнить представление вершины, и добавит стоимость пройденного пути, то в переборах и в оценках появятся числа у вершин, это сколько до них уже пройдено. Если меня интересует самый короткий путь, то я должен смотреть и оценивать те пути из тех точек, для которых путь минимальный. Т.е. чем меньше я путь прошел, тем больше у меня оснований считать, что если я прибавлю очередную, то это самый короткий будет путь. Если я приму такой аргумент за основу, и буду использовать те же списки открытых и закрытых, а из списка буду выбирать те, у которых цена меньше, то я получу алгоритм полного перебора с ценой, более того это интересный алгоритм. Этот алгоритм всегда найдет путь, если он есть, а первый путь, который он найдет, будет путем минимальной длины. А программировать очень просто. Если вы нашли первую вершину, а потом она повторяется, отбрасывать ту, которая пришла опасно. Потому, что вдруг вы до нее нашли путь меньше. Значит нужно оставить ту из этих двух, путь до которой меньше. А дерево у вас или сеть уже пропадает.