Максимално претеглен път между два върха в насочен ацикличен Графика - алгоритъм, графика, теория на графиките, насочени ациклични графики

Обичайте някои насоки по този проблем:

G е насочена ациклична графика. Искате да преминете от връх c до връх z. Някои ръбове намаляват печалбата ви, а някои увеличават печалбата ви. Как стигате от c до z, като максимизирате печалбата си. Каква е сложността на времето?

Благодаря!

Отговори:

1 за отговор № 1

Проблемът има оптимална подструктура. За да намерите най-дългия път от върха c до върха z, първо трябва да намерим най-дългия път c на всички предшественици на z, Всеки проблем от тях е друг по - малък подпроблем (най - дългия път от c към конкретен предшественик).

Даваме предшествениците на z като u1,u2,...,uk и dist[z] да бъде най-дългия път от c да се z тогава dist[z]=max(dist[ui]+w(ui,z))..

Ето илюстрация с 3 предшественици, които пропускат теглата на ръбовете:

Така че, за да намерите най-дългия път към z ние първо трябва да намерим най-дългия път към своите предшественици и да вземем максимума над тях (техните стойности плюс техните ръбове тежести до z).

Това изисква винаги, когато посещаваме връх u, всички uпредшествениците му трябва да са били анализирани и изчислени.

Така че въпросът е: за всеки връх u, как да се уверим, че след като сме настроили dist[u], dist[u] никога няма да бъде променена по-късно? Сложете го по друг начин: как да се уверите, че сме разгледали всички пътеки c да се u преди да се вземе предвид всеки ръб с произход от u?

Тъй като графиката е ациклична, можем да гарантираме товасъстояние чрез намиране на топологичен сортиране по графиката. топологичният сортинг е като верига от върхове, където всички краища се отнасят отляво надясно. Така че, ако сме на върха vi след това разгледахме всички водещи пътеки vi и имат крайната стойност на dist[vi].

Сложността на времето: топологичен сорт отнема O(V+E), В най-лошия случай z е лист и всички други върхове сочат към него, ще посетим всички графични ръбове, които дава O(V+E).

---

0 за отговор № 2

Позволявам F (ф) бъдете максималната печалба, от която можете да отидете ° С да се ф във вашия DAG. След това искате да изчислите е (Z), Това може лесно да бъде изчислено в линейно време, използвайки динамично програмиране / топологично сортиране.

Инициализиране f (u) = - безкрайност за всеки ф различни от ° С, и f (c) = 0, След това продължете да изчислявате стойностите на е в някакъв топологичен ред на вашия DAG. По този начин, тъй като редът е топологичен, за всеки входящ край на възела се изчисляват, другите крайни точки се изчисляват, така че просто изберете максималната възможна стойност за тази възлова точка, т.е. f (u) = макс (f (v) + цена (v, u)) за всеки входящ край (v, u).

---

0 за отговор № 3

По-добре да го използвате Топологично сортиране вместо Белман Форд тъй като неговата DAG.

Източник: - http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf

РЕДАКТИРАНЕ:-

G е DAG с отрицателни краища.

Някои ръбове намаляват печалбата ви, а някои увеличават печалбата ви

• Edges - увеличаване на печалбата - положителна стойност
• Edges - намаляване на печалбата - отрицателна стойност

След TS, за всеки връх U в TS ред - отпуснете всеки изходящ край.

dist[] = {-INF, -INF, ….}
dist[c] = 0 // source

for every vertex u in topological order
if (u == z) break; // dest vertex
for every adjacent vertex v of u
if (dist[v] < (dist[u] + weight(u, v))) // < for longest path = max profit
dist[v] = dist[u] + weight(u, v)

ans = dist[z];

---