Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...
Aşamalı olarak yapılandırılmış yönlü graflarda (Directed Stage Graphs) kaynaktan hedefe en kısa yolu ileri (Forward) veya geri (Backward) formüllerle bulan dinamik programlama yöntemidir.
Çok Aşamalı Graf (Multistage Graph), köşe kümelerinin birbirini izleyen $k$ adet aşamaya (stages) ayrıldığı ve kenarların sadece aşama $i$ köşe kümesinden aşama $i+1$ köşe kümesine doğru yönlendiği özel bir Yönlü Döngüsüz Graftır (DAG).
Kaynaktan (Stage 1) hedefe (Stage k) giden en kısa yol, dinamik programlama kullanılarak çözülür. İleri Akış (Forward) yaklaşımı, hedef düğümden başlayarak geriye doğru maliyetleri hesaplar; her düğümün hedefe olan en kısa mesafesini bulur.
Geri Akış (Backward) yaklaşımı ise kaynaktan başlayarak ileriye doğru maliyetleri yığar ve hedefe kadar olan optimum kararları hesaplar. Her iki yaklaşım da en sonunda aynı optimal yolu üretir.
Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.
1export interface MultistageEdge {2 u: number;3 v: number;4 weight: number;5}67export function forwardMultistage(8 n: number, // Total number of vertices (1-indexed, target is n)9 edges: MultistageEdge[]10): { cost: number; path: number[] } {11 const cost = new Array(n + 1).fill(Infinity);12 const d = new Array(n + 1).fill(0);13 cost[n] = 0;14 15 // Group edges by source for fast lookup16 const adj: Record = {}; 17 for (const edge of edges) {18 if (!adj[edge.u]) adj[edge.u] = [];19 adj[edge.u].push({ v: edge.v, w: edge.weight });20 }21 22 // Forward DP: iterate vertices backwards23 for (let i = n - 1; i >= 1; i--) {24 if (!adj[i]) continue;25 for (const edge of adj[i]) {26 const val = edge.w + cost[edge.v];27 if (val < cost[i]) {28 cost[i] = val;29 d[i] = edge.v;30 }31 }32 }33 34 // Reconstruct path35 const path: number[] = [1];36 let curr = 1;37 while (curr !== n && d[curr] !== 0) {38 curr = d[curr];39 path.push(curr);40 }41 42 return { cost: cost[1], path };43}Aşamalardan oluşan yönlü bir graf girerek İleri (Forward) ve Geri (Backward) DP adımlarını adım adım simüle edin.
Aşamalardan oluşan yönlü bir graf girerek İleri (Forward) ve Geri (Backward) DP adımlarını adım adım simüle edin.
En İyi Durum: O(V + E) - Aşamalı yapıda doğrusal
Ortalama Durum: O(V + E)
En Kötü Durum: O(V + E) - Tüm kenar ve düğümler taranır
O(V) - cost ve karar dizileri için - Bu algoritmanın karmaşıklığı belirtilmemiş.
Çok Aşamalı Graflar (Multistage Graphs) Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar: