Какой алгоритм обхода графа я должен использовать для этого?

Question

Мне нужно пройти ориентированный граф определенным образом, и я не уверен, какой алгоритм использовать. Возможно, Stackoverflow может помочь.

Ситуация - У меня есть ориентированный граф, где у ребер есть номер, связанный с ними. Давайте предположим, что это число измеряется в футах, милях, ..., что угодно. Я бы хотел пройти от начального узла и найти все ребра, которые находятся на некотором определенном расстоянии от начального узла

Например, я хочу начать с какого-то узла и пройти по графику и найти каждый край, где я прошел 100 миль от начала. Например (2), start_node ---- ребро-1 (80 миль) ---> узел (2) ---- ребро-2 (40 миль) ---> узел (3) --- ребро-3 (50 миль) - - start_node ---- edge-4 (40 миль) ---> узел (4) ---- edge-5 (70 миль) ---> node (5) --- edge-6 (50 миль) - -

Начиная с start_node и пройдя 100 миль, ответ будет: edge-2, edge-5. Любые мысли о том, какой алгоритм обхода я должен использовать / рассмотреть?

Спасибо

Answer 1

Я бы выбрал Алгоритм Дейкстры . Просто остановитесь, когда путь к последнему отмеченному узлу больше заданного.

Answer 2

Предполагая, что никакое ребро не может быть пройдено более одного раза, ваша проблема является обобщением задачи Longest Path , которая является NP-трудной.Следовательно, подходы с полиномиальным временем, такие как алгоритм Дейкстры, не будут работать.

Если ваш граф не очень большой, вы можете заняться динамическим программированием: таблица D [v, k], которая хранит каждую вершину v и каждуючисло ребер все возможные расстояния от корня до v с k ребрами, плюс все возможные предшественники для каждого возможного расстояния.D [v, k] может быть заполнено, если D [v, k-1] сделано.Вы повторяете это до тех пор, пока никакое расстояние не станет ниже 100, а затем вы сможете откатиться от каждой вершины, которая достигла стоимости ровно 100.

Answer 3

алгоритм Дейкстры .

Answer 4

Я думаю, вы можете использовать что-то похожее на алгоритм Дейкстры

http://en.wikipedia.org/wiki/Dijkstra's_algorithm