Pengaturcaraan Graf Dinamik

Error

Dalam penyelesaian menggunakan pengaturcaraan dinamik, urutan pengiraan dinamik adalah penting (perlu nilai yang bergantung pada semasa dikira sebelum ini).
Oleh itu, jika perlu menggunakan pengaturcaraan dinamik pada graf akiklik terarah, pada mulanya perlu membina pengisihan topologi graf. Kemudian hitung dinamik dengan mengisih melalui bucu dalam susunan jenis topologi yang dibina (bergantung pada masalah, susunan traversal boleh sama ada dari sumber ke sink atau sebaliknya).
 
 

Jika graf mengandungi kitaran (tiada jenis topologi), maka dua helah boleh membantu:

1) Kira dinamik n kali, dengan n ialah bilangan bucu dalam graf (dengan analogi dengan algoritma Ford-Bellman). Tetapi ini meningkatkan asimptotik dan jarang berkesan secara umum.

2) Bina graf pemeluwapan. Bagi setiap komponen graf asal yang bersambung kuat, selesaikan masalah secara berasingan. Graf pekat adalah asiklik dan untuk itu anda boleh menggunakan pendekatan standard dengan pengisihan topologi, sambil menggunakan sebagai nilai puncak, nilai yang dikira untuk komponen yang bersambung kuat. Kaedah ini digunakan terutamanya.