If this graph is converted to some other graph where cycles are not allowed, this problem can be solved using the Dijkstra algorithm .
To do this, start by dividing the lines by 7. Look at this sequence: 1, 10, 100, ... (mod 7). Since 7 is a prime number, 10 7-1 = 1 (mod 7) due to the small Fermat's theorem . This means that the sequence 1, 10, 100, ... (mod 7) is periodic, and the period is 6. This will be used to transform the graph, and it also allows you to recursively calculate S n (mod 7) using S n- 1 (mod 7): S n = S n-1 + 10 n% 6 * n_th_digit (mod 7).
You need to start searching for the shortest path from node N, because this path can be completed on one of several nodes of the transformed graph. It also allows you to quickly determine (using the first 2 nodes of the path) if you are allowed to visit node "5", node "4" and other "even" nodes.
The open dialing algorithm (priority queue) must contain the priority itself (sum of digits) if 3 additional bits and 3 remainders are allowed: “4”, “visited 3”, “7” visited, S % 3 , S % 7 and S.length % 6 .
The schedule should be converted as follows. Each vertex is expanded to 3 vertices, one is allowed only for S%3==0 , the other for S%3==1 and S%3==2 . Then each vertex decomposes to 7 (for S%7 ), and then each vertex decomposes to 6 (for S.length % 6 ). You can put all of these extensions into the source graph: just add a 3D array (size 3 * 7 * 6) of back pointers to each node. When searching for the shortest path, non-empty backward pointers define a closed set of algorithms (they prohibit loops). When the shortest path is found, reverse pointers allow you to restore the sequence of nodes in this path. And the moment when the shortest path is found is determined by visiting node 1 with (node_3_not_visited || S%3==0) && (node_7_not_visited || S%7==0) .