Looking for an algorithm to find a shortest path in a special graph
The "state" of a traversal (after visiting $k$ edges) is the set of $k$ edges that you've traversed so far, in the order they were traversed.  You can now use any method for exploring this state space: e.g., BFS; or A*, if you have a suitable heuristic.

In other words, we define a new graph $G'$ where each vertex of $G'$ is a possible state of a traversal (after visiting some number of edges), and where there is an edge $u \to v$ if starting from state $u$ it is possible to add one edge to the end to reach state $v$.  Then you do BFS in $G'$.  You don't need to build up $G'$ explicitly before doing BFS; the graph can be represented implicitly (where each time you reach a state $u$, you can compute all possible next-states reachable from $u$ in a single step).

If BFS takes too much memory, you can use techniques from explicit-state model checking.  This will reduce the space consumption but not the memory usage.

None of this avoids the fact that, for arbitrary functions $f,g$, the running time of these algorithms might all be exponential in the worst case, because you might need to explore an exponentially-sized state space.  I suspect the only hope to do better is to take advantage of knowledge of some particular structure in $f,g$.