Count paths with Topological Sort

Question

У меня есть DAG, и мне нужно подсчитать все пути с любого узла на другой узел, я немного изучил его, и я обнаружил, что это можно сделать с помощью некоторого топологического порядка, но до сих пор решения являются неполными или неправильными.

Итак, как правильно это сделать ?.

Спасибо.

Answer 1

Вы можете использовать рекурсию для подсчета всех путей в дереве/DAG. Вот псевдокод:

function numPaths(node1, node2): 
    // base case, one path from node to itself 
    if (node1 == node2): return 1 

    totalPaths = 0 
    for edge in node1.edges: 
     nextNode = edge.destinationNode 
     totalPaths += numPaths(nextNode, node2) 

    return totalPaths 

Edit: Хороший динамичный подход к решению этой проблемы является Floyd-Warshall algorithm.

Answer 2

Assume G(V,E) 
Let d[i][j] = the number of all the paths from i to j 
Then d[i][j]= sigma d[next][j] for all (i,next) in E 

Это кажется слишком медленным? Хорошо. Просто запомните это (некоторые ребята называют это динамическим программированием). Например,

memset(d,-1,sizeof(d))// set all of elements of array d to -1 at the very beginning 
saya(int i,int j) 
{ 
    if (d[i][j]!=-1) return d[i][j];//d[i][j] has been calculated 
    if (i==j) return d[i][j]=1;//trivival cases 
    d[i][j]=0; 
    for e in i.edges 
     d[i][j]+=saya(e.next,j); 
    return d[i][j]; 
} 

Теперь saya (i, j) вернет число всех путей от i до j.

Answer 3

Поскольку это DAG, вы можете топологически отсортировать узлы в O (V + E) времени. Предположим, что исходной вершиной является S. Затем из S начинаем сначала обходить узлы по глубине. Когда мы обрабатываем узел U, допустим, что существует ребро U-> V, тогда V, конечно, еще не посещено (почему? Потому что это ориентированный ациклический граф). Таким образом, вы можете достичь от S до V через узел U в d [U ], где d [U] - количество путей от S до U.

Так много путей от S до любого узла V, d [V] = d [x1] + d [x2] + d [x3] ] +. , , + d [xy], где есть ребро, подобное x1-> V, x2-> V,. , , xy-> V

Этот алгоритм возьмет O (V + E), чтобы топологически отсортировать граф, а затем для вычисления количества путей не более O (V * E). Вы можете дополнительно сократить время выполнения вычисления количества путей до O (V + E), используя список смежности вместо матрицы смежности, и это наиболее эффективное решение до сих пор.