How to find the shortest path on a graph that satisfies certain conditions?

Question

Programming

In general, the task is as follows:
It is necessary to find the shortest path on an undirected graph with non-negative weights of edges and nodes that does not violate certain rules. You can determine whether the path violates the rule using a certain boolean function isValid(Subpath x) which takes the entire path or part of it as input. If part of the path is not valid, then the entire path is not valid either.
Example 1:
Find the shortest path in which edges or nodes with a certain value of some attribute do not occur more than N times in a row.
Example 2:
Find the shortest path where the nodes must not be included in any particular order.
The first thing that came to my mind was to take Dijkstra's algorithm and add an isValid call before calculating the weight of the subpath. If the subpath is invalid, we reject it. This works for simple examples, but in principle the approach is wrong.
For example, we have a graph shown in the picture, we are looking for a path from 1 to 6, the weights are written on the edges. Let's say that there are some rules forbidding that there are nodes in the path in the order 1-2-3 and 1-2-5.
Using Dijkstra's algorithm with subpath filtering, we find the path 1-3-4-5-6 with a total cost of 330, although the shortest path: 1-3-2-5-6, with a total cost of 170.

Another option: use Yen's algorithmbut change the exit condition from the outer loop: look not for K paths, but for the first path for which isValid == true. This should work, but the complexity of the algorithm is high, there will be problems with the running time.
Maybe someone knows some ready-made solutions, the task is not so exotic.

Answer 1

You can search for the shortest path using a recursive SQL query (last sections 7 and 8). I don't know about the speed (actually, MS SQL Server is a fast machine. Although some people write that recursion is evil, because it is considered slow. In short - check), but you can insert any conditions into the query.