Самый длинный путь между источником и определенными узлами в группе обеспечения доступности баз данных

Question

Как мне найти самый длинный путь от одного источника ко всем конечным пунктам назначения т.е. для источника i1, дайте самый длинный путь между i1 -> o1 и i1 -> o2.

Легенды, описанные на приведенном выше графике, таковы: (i1, i2) - начальные узлы (o1, o2) являются конечными узлами (1-8) подграфы Края могут иметь вес + ive / -ive

Самые длинные пути в этой сети расположены в следующем порядке:

Наихудший путь: i1 -> 1 -> 4 -> o1

Тогда все пути i1… ->… o1

Тогда i1 -> 5 -> 6 -> o2

Нужен способ игнорировать выбор (i1 -> 3) или (3 -> 4) подсетей, даже если они длиннее, чем i1 -> 5

Answer 1

Википедия на помощь! Их страница по этой проблеме указывает, что в общем случае ваша проблема - NP-Complete. Однако, поскольку у вас есть направленный ациклический граф, вы можете инвертировать все веса ребер и запустить алгоритм Беллмана-Форда для его решения. Алгоритм B-F обычно вычисляет кратчайшие пути из одного источника в графе. С перевернутыми весами ребер он должен давать самые длинные пути.

Answer 2

Я полагаю, что следующее даст вам наибольшее количество шагов для достижения пункта назначения (не фактический путь, а просто количество шагов). Это не учитывает вес ребра. Это работает путем объединения узлов, начиная с src до тех пор, пока не останется никаких соседей, кроме узла назначения.

longestPath (src, dest) =
    if (neighbors(src) == [dest]) then 1
    else 1 + longestPath(newNode(concat (map neighbors (neighbors src))), dest)