Given an arbitrary connected graph with a start and goal node, with both directed and undirected edges, where each edge has a maximum number of times it may be traversed during a single traversal (at least 1, at most infinite): Is it possible to confirm in O(n) time whether or not a walk (possibly with repeating edges and/or nodes) exists such that the walk stops at a node N before reaching the goal due to not being allowed to traverse any of N's edges additional times? For clarification: I'm wondering if it's possible to traverse the graph in such a way that I end up at a node in the graph that no longer has a path to the goal node (due to the edges along those paths no longer allowing additional traversal). This assumes that at least one walk between start and goal existed when the traversal began.Example: A graph with edges S~A, A~B, B~C, C~G, C~>A (S = start, G = goal).If the edge B~C only allows the user to traverse it once, then a valid walk from S to G would be S, A, B, C, G. However, moving from C back to A would prevent the user from reaching the goal since C~>A is directed, and B~C has already been traversed the maximum number of times. I'm looking for a way to confirm the existance of such an invalid walk.
Finding an invalid walk order between two nodes when edges have traversal limits
algorithms;graphs