Note de curs, probleme algoritmică, 25 noiembrie 2013

În acest curs am discutat despre problema 1450 - Russian Pipelines.

Cerința

Dându-se un graf orientat aciclic (DAG - Directed Acyclic Graph) cu muchii ponderate (cu costuri) să se calculeze cel mai lung drum dintre două noduri date (sau să se determine dacă nu există niciun astfel de drum).

Sortarea topologică

Nodurile oricărui graf orientat aciclic pot fi sortate topologic.

Nodurile unui graf sunt sortate topologic dacă toate muchiile sunt orientate de la un nod către un alt nod care apare după nodul inițial în sortarea topologică.

Exemplu

6 noduri cu muchiile:
6 -> 5
1 -> 4
1 -> 2
3 -> 1
2 -> 4
6 -> 3
6 -> 1

Pot fi sortate topologic astfel:
6 5 3 1 2 4

Soluția

Se sortează topologic nodurile grafului și apoi se realizează o dinamică pe ele.

Mai exact, pentru fiecare nod se calculează lungimea maximă posibilă a unui drum de la nodul de început la nodul curent. Dinamica este posibilă tocmai datorită proprietății sortării topologice (toate muchiile sunt orientate de la stânga spre dreapta). Sortarea topologică dictează ordinea în care trebuie să se calculeze recurența dinamicii.

Reconstituirea soluției

Deși problema nu cere, lanțul de lungime maximă poate fi reconstituit prin memorarea, pentru fiecare nod, a ultimei muchii (nodul de proveniență) care a contribuit la obținerea lungimii maxime.