patternMinor
Looking for an algorithm to find a shortest path in a special graph
Viewed 0 times
pathgraphshortestalgorithmlookingspecialforfind
Problem
I have the following problem: given a directed unweighted graph and a set of source vertices, it's needed to find the shortest path to the specified vertex. The mentioned graph has two special extensions:
-
A graph's edge can be active or inactive depending on edges placed in the path before. In other words, the edge $E$ can be placed in the path at position $i$ only when $ f( E, path[1..i-1] )$ is true. The $f$ function in not specified explicitly; each path has a corresponding set of named properties and each graph edge has a function which modifies property values if the edge is involved (placed in the path). The edge $T$ is active (i.e. can be inserted in the path) if $g(T, set\ of\ properties)$ is true. A property may have a boolean or enum value, but it is desirable for me to allow properties to have integer and string values too.
-
Two adjacent edges in a path are not required to be linked. I.e. $path[j].end$ is not necessary equal to $path[j+1].start$. For example, we want to add the edge $B$ to the path and it has a property requirement which can only be satisfied if the edge $A$ is placed in the path before the $B$. In this case a $path[j]$ edge equals to the $A$ and $path[j+1]$ edge corresponds to the $B$. Still, $path[j+1].start$ should be equal to at least one of $path[1..j+1].end$ vertices.
The graph examples I've seen are sparse and pretty small (several dozen vertices). However some paths may contain up to several thousands of edges to satisfy the complex transition rules.
My current solution to this problem is based on the BFS algorithm. First, I construct a new graph where each vertex represents a vertex in the source graph plus the current path and it's property values. This is similar to how a game like Chess can be represented as a graph: a set of vertices each describing a current state of the game and a set of edges which describe the possible actions. Then, I simply use the BFS to find the shortest path. This approach has several drawba
-
A graph's edge can be active or inactive depending on edges placed in the path before. In other words, the edge $E$ can be placed in the path at position $i$ only when $ f( E, path[1..i-1] )$ is true. The $f$ function in not specified explicitly; each path has a corresponding set of named properties and each graph edge has a function which modifies property values if the edge is involved (placed in the path). The edge $T$ is active (i.e. can be inserted in the path) if $g(T, set\ of\ properties)$ is true. A property may have a boolean or enum value, but it is desirable for me to allow properties to have integer and string values too.
-
Two adjacent edges in a path are not required to be linked. I.e. $path[j].end$ is not necessary equal to $path[j+1].start$. For example, we want to add the edge $B$ to the path and it has a property requirement which can only be satisfied if the edge $A$ is placed in the path before the $B$. In this case a $path[j]$ edge equals to the $A$ and $path[j+1]$ edge corresponds to the $B$. Still, $path[j+1].start$ should be equal to at least one of $path[1..j+1].end$ vertices.
The graph examples I've seen are sparse and pretty small (several dozen vertices). However some paths may contain up to several thousands of edges to satisfy the complex transition rules.
My current solution to this problem is based on the BFS algorithm. First, I construct a new graph where each vertex represents a vertex in the source graph plus the current path and it's property values. This is similar to how a game like Chess can be represented as a graph: a set of vertices each describing a current state of the game and a set of edges which describe the possible actions. Then, I simply use the BFS to find the shortest path. This approach has several drawba
Solution
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$.
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$.
Context
StackExchange Computer Science Q#71268, answer score: 2
Revisions (0)
No revisions yet.