It is necessary to find all the paths between any two vertices of the graph. It is not clear how to do this.

  • no way. Their number can be of the order of factorial from the vertices. - pavel
  • @pavel: But this does not negate the potential opportunity? Unless, of course, there are no cycles. - VladD
  • @VladD well then recursion and forward) - pavel
  • @pavel: BFS soon? - VladD
  • @VladD Then this is a modified BFS, which visits the already visited peaks ... - Harry

1 answer 1

Source - poorly searched, if not found

Well, and this is solved simply by dynamic programming. Let s and t be the initial and final vertices. First, delete from the graph all vertices that cannot be reached from s, and all vertices from which t cannot be reached. Topologically sort the graph. If it contains a cycle (which is equivalent to the absence of top. Sorting), then the number of paths is infinite - you can always go around the cycle.

After topological sorting, the vertices of the graph will be renumbered from 1 to N, so that the vertex s will get number 1 (since all vertices are reachable from it), and the vertex t is the number N, and all edges are oriented from the vertex with a smaller number to the top with large numbers (by definition top. sorting).

Let's get an array a[1..N] , such that the element a[x] contains the number of paths from x to t , and calculate its contents, using the formulas:
a[N] = 1 .
For x < N : a[x] = the sum of a[y] for all y , such that there is an edge (x, y) . After that, a[1] will be the answer.

  • In the sense of "delete from the graph all vertices that are unattainable from s, and all vertices from which t cannot be reached". If we delete each vertex that is not incident to s and t, then in the general case we get 2 non-connected subgraphs. Or did I not understand something? - sm4ll_3gg
  • @ sm4ll_3gg There can be no way from distant vertices ... - ThusMad
  • In the sense of? If I delete all vertices that are not incident to the vertices of the beginning and the end, then I will lose all the ways - sm4ll_3gg
  • @ sm4ll_3gg Well, if you can’t reach b from the vertex a, then why do you need a - Thus Mad
  • But if we can reach the top c from the top a, from which the top b can reach, then we cannot remove it, and with this algorithm we remove it - sm4ll_3gg