Самый короткий путь в графе приоритета

Question

Я ищу алгоритм для определения кратчайшего пути графа приоритета с учетом графика соединений. Я посмотрел на Дейкстра и Беллмана Форда, но я не думаю, что они жизнеспособны для графа приоритетов, потому что они только выходят наружу через один край в каждой вершине. Но в графе приоритета также есть случаи, когда вам нужно пройти через два или более ребра, чтобы достичь следующей вершины. Например, для демонтажа вам необходимо сначала удалить детали A и B, так как вы можете добраться до части C.

То, что я пытаюсь решить: У меня есть простой график приоритета, представляющий, как разобрать продукт. Каждая вершина имеет стоимость (единицы времени). На этом графике у меня есть начало и назначение. Результатом должно быть минимальное время, необходимое для разборки.

Также следует учитывать, что вы можете разобрать moules в целом для достижения определенной части в зависимости от графика соединения. Этот график показывает, как части фактически связаны друг с другом. Как A, B и C необходимо удалить, чтобы достичь D. Сначала необходимо удалить A. Затем вы можете удалить B и C в целом (удаление C, пока B все еще привязано к нему).

Answer 1

Теперь я использовал алгоритм поиска Deep-first с некоторыми изменениями, соответствующими моей цели для первой части. Вторая часть, где также следует рассматривать разбор модулей, а не каждый мир, по-прежнему отсутствует. Возможно, с некоторыми дополнительными изменениями в алгоритме это тоже возможно.