Algoritma yang menemukan jumlah jalur sederhana dari ke di

Can anyone menyarankan saya algoritma waktu linear yang mengambil sebagai masukan diarahkan asiklik grafik dan dua simpul dan dan kembali jumlah jalur sederhana dari ke di . Saya memiliki algoritma di mana saya akan menjalankan DFS (Depth First Search) tetapi jika DFS menemukan maka tidak akan mengubah warna (dari putih menjadi abu-abu) dari salah satu node yang ada di jalur sehingga jika ini adalah subpath dari jalur lain maka DFS juga akan melalui subpath ini lagi. Sebagai contoh pertimbangkan daftar adjacency di mana kita perlu menemukan jumlah path dari p ke v .$G=(V,E)$$s$$t$$s$$t$$G$
$t$$s \rightsquigarrow t$$p$$v$

$$\begin{array}{|c|c c c|} \hline p &o &s &z \\ \hline o &r &s &v\\ \hline s &r \\ \hline r &y \\ \hline y &v \\ \hline v &w \\ \hline z & \\ \hline w &z \\ \hline \end{array}$$ Di sini DFS akan mulai dengan $p$ dan kemudian katakanlah ia pergi ke $p \rightsquigarrow z$ karena tidak menemukan $v$ DFS akan berjalan secara normal. Sekarang kedua path adalah $psryv$ karena ia bertemu $v$ kita tidak akan mengubah warna simpul $s,r,y,v$ ke grey. Lalu path $pov$ karena warna $v$ masih putih. Lalu path $posryv$ karena warna $s$ putih dan sama dengan path $poryv$.Juga counter dipertahankan yang bertambah ketika $v$ ditemui.

Apakah algoritme saya benar? jika tidak, modifikasi apa yang diperlukan untuk membuatnya benar atau pendekatan lain akan sangat dihargai.

Catatan : Di sini saya telah mempertimbangkan algoritma DFS yang diberikan dalam buku "Pengantar algoritma oleh Cormen" di mana ia mewarnai node sesuai dengan statusnya. Jadi jika node belum dikunjungi, belum dieksplorasi dan dieksplorasi maka warnanya akan menjadi putih, abu-abu dan hitam masing-masing. Semua hal lain adalah standar.

Implementasi Anda saat ini akan menghitung jumlah jalur yang benar dalam DAG. Namun, dengan tidak menandai jalur, ini akan membutuhkan waktu yang eksponensial. Misalnya, dalam ilustrasi di bawah ini, setiap tahap DAG meningkatkan jumlah total lintasan dengan kelipatan 3. Pertumbuhan eksponensial ini dapat ditangani dengan pemrograman dinamis.

Menghitung jumlah jalur - dalam DAG diberikan oleh pengulangan, $s$$t$

$$\text{Paths}(u) = \begin{cases} 1 & \text{if } u = t \\ \sum_{(u,v) \in E} \text{Paths}(v) & \text{otherwise.}\\ \end{cases}$$

Modifikasi sederhana DFS akan menghitung ini diberikan sebagai

def dfs(u, t):
    if u == t:
        return 1
    else:
        if not u.npaths:
            # assume sum returns 0 if u has no children
            u.npaths = sum(dfs(c, t) for c in u.children)
        return u.npaths

Tidaklah sulit untuk melihat bahwa setiap sisi dilihat hanya satu kali saja, karenanya merupakan runtime dari .$O(V + E)$

Anda hanya perlu memperhatikan bahwa jumlah jalur dari satu simpul ke simpul target adalah jumlah dari jumlah jalur dari anak-anaknya ke target. Anda tahu bahwa algoritma ini akan selalu berhenti karena grafik Anda tidak memiliki siklus.

Sekarang, jika Anda menyimpan jumlah jalur dari satu node ke target saat Anda mengunjungi node, kompleksitas waktu menjadi linear dalam jumlah simpul dan memori linear dalam jumlah node.

Jumlah jalur antara dua simpul dalam DAG dapat ditemukan menggunakan representasi matriks adjacency.

Misalkan A adalah matriks adjacency dari G. Mengambil kekuatan Kth dari A setelah menambahkan matriks identitas ke dalamnya, memberikan jumlah lintasan panjang <= K.

Karena panjang maks dari setiap jalur sederhana dalam DAG adalah | V | -1, menghitung daya | V | -1 akan memberikan jumlah jalur antara semua pasangan simpul.

Menghitung | V | -1 th kekuatan dapat dilakukan dengan melakukan muliplications log (| V | -1) masing-masing TC: | V | ^ 2.