How to find the number of paths in an unweighted graph with symbols at the nodes?

Question

.NET

Hello! I just can not understand the algorithms for finding paths in graphs. I ask you for help.
A graph is a diagram of roads, where nodes are cities. You need to find the longest path from A to M and the total number of paths.

I understand that you need to use depth first search here, but I read that it just finds the longest path. And I also need it to count the number of possible paths from A to M. Thanks in advance! I would be grateful for any explanations.

Answer 1

Just like looking for the longest path. You will have DFS, which returns the number of paths from a given vertex to the final one, with already visited vertices given. In it, iterate over all outgoing edges, run recursively (if the end of the edge has not already been visited), and sum up all the results. If you came to the final vertex, then return 1 (1 path of length 0 - already arrived). At the beginning of the function, mark the vertex as visited so that you do not enter it again. At the end of the function, mark the vertex as not visited so that other paths through this vertex can be counted. The difference with the longest path is that you are summing up the results of all recursive DFS calls here, rather than taking the maximum. Well, you don’t need to add +1, as to the length, to add.
If the graph is acyclic, then memoization can be used: save the results of the DFS calculation for each initial vertex (in a global array, for example) and never read it again. On each call, check to see if the value has already been calculated and return it.