圖算法來算

Question

我試圖找到時間效率的算法不同的起始頂點和一個結束點之間的所有可能的路徑爲以下任務

給定一組網頁A，B，C，d， E其中A，B，C，D可以是起點，但E 將始終是終點。以下代表頁面 （A，B），（A，B），（A，C），（A，E），（B，A），（B，C），（C，A）， C，E），（C，D），（D，E），（D，A）。 現在，如果我選擇A作爲起點，並且E作爲終點，那麼我必須找到所有 之間的可能路徑，其路徑長度至多爲4，其時間效率爲 。所以至多路長度4 A和E與之間的所有可能路徑是

A->電子

A-> D->電子

A-> C-> D->電子

A-> B-> C->電子

A-> B-> C->電子

A-> B-> A->電子 等等

注1： 兩個相同的頂點之間的兩條邊都被視爲不同，也爲了頂點也很重要的。 Graph中可以存在一個循環。

注2： 只有破壞無限循環搜索的方法是通過限制路徑長度的最大限制。

Answer 1

這個問題可以通過動態編程來解決。

我們可以表示每個步驟由兩個參數，當前節點和步驟的其已經採取的數目（節點，步驟）

僞代碼：

int[][]dp; 
int getNumberOfWay(int node, int step){ 
    if(step == 4) 
     if(node == end node) 
     return 1; 
     return 0; 

    if(already visit this step) 
     return dp[node][step]; 
    int result = 0; 
    if(node == end node) 
     result++; 
    for(node that has edges coming from this node) 
     result += getNumberOfWay(next node, step + 1); 
    return dp[node][step] = result; 
} 

此時間複雜度是O （4 * E * N）其中E是邊數，N是節點數。

注意：如果我們遍歷來自末端節點的圖，而不是4個開始節點，問題也可以得到改善。

Answer 2

它可以使用矩陣乘法來解決。

假設A[i][j]表示從i到j的總行程，則由於組合的乘法規則，我們有A'[i][j] = A[i][k] * A[k][j]。我們可以看到這個公式是以矩陣乘法的形式出現的。

因此，我們可以使用N行和列構造矩陣A，其中N是總頁數。然後A[i][j]表示從i開始到j的初始路徑。例如，對於您的問題初步A將是：

A B C D E 
A 0 2 1 0 1 
B 1 0 1 0 0 
C 1 0 0 1 1 
D 1 0 0 0 1 
E 0 0 0 0 0 

接下來，我們只需要計算A[0..3][4] + A^2[0..3][4] + A^3[0..3][4] + A^4[0..3][4]，其中A^k意味着A至k力量。

使用矩陣乘法的好處是它可以擴展到更一般的問題：使用精確的K步可以形成從i到j的多少路徑？。

在這種情況下，我們只需要計算A^k，它可以使用exponentiation by squaring有待加快和O(log k) * O(N^3)，其中O(N^3)是矩陣乘法的複雜解決。