<p>First, let's define/simplify the situation or condition.</p>
<p>We have a graph with vertices and edges.
Some edges are special, they open up (get activated) only after waiting for some time at the source.</p>
<p>This waiting time is spent by taking a cycle tour.
Start from the current node, follow some other edges (hopefully normal edges), and finally reach back to the current node. Now check whether the special edge has opened up else take the cycle again.</p>
<p>The exact number of cycles required to activate each special edge is known (specified).</p>
<p><strong>The problem is to find the shortest path from a source to a destination vertex in this graph.</strong></p>
<p>Let's see how to solve this problem using an example.</p>
<p><a href="https://i.sstatic.net/MUuiCYpB.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/MUuiCYpB.png" alt="Example" /></a></p>
<p>We have a graph G with</p>
<p>6 vertices (A, B, C, D, E, F)</p>
<p>6 normal edges (source, destination, cost)</p>
<p>1 special edge (source, destination, cost, number of cycles to activate it)</p>
<p>The goal is to find the shortest path (and cost) from A to E.</p>
<p>B-E is the special edge. But to activate it, we have to visit B, 2 times. Before taking B-E,
we have to traverse (B-C-D-B) 2 times. This cycle path can be determined by finding the shortest path from B to B (assuming no self-loops in the graph).</p>
<p>For each special edge's source vertex, calculate (and save) the cycle path and cost of taking that cycle path for the required number of times (waiting cost).</p>
<p>Now we can convert the special edges to normal edges by adding the calculated waiting cost to the original cost of that edge.</p>
<p>Original cost of B-E is 1.
Cost of cycle B-C-D-B is 3.
Taking this cycle for 2 times will give total waiting cost as 3*2=6.
The updated cost of B-E is 1 + 6 = 7.</p>
<p>Now this graph becomes a normal graph (but there is a catch).</p>
<p><a href="https://i.sstatic.net/KyWgp4Gy.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/KyWgp4Gy.png" alt="temporary graph" /></a></p>
<p>Find shortest path from A to E on this graph.
You get A-B-E, the cost is 1 + 7 = 8.</p>
<p>The cost is final, but the actual path must include cycle path also.</p>
<p>Replace each special edge with its cycle path (which we have already computed) repeated given number of times to activate the edge</p>
<p>A-<strong>B-E</strong> becomes A-<strong>B-C-D-B-C-D-B-E</strong></p>
<p>This answer may not be a complete solution but may work as a good starting point.</p>

CC BY-SA 4.0
2024-08-26T10:32:01.720Z
2024-08-26T10:32:01.720Z
Sreeragh A R
<p>Given a directed graph <span class="math-container">$G(V, E)$</span>, I want to find a route, <span class="math-container">$R \in E^*$</span> from <span class="math-container">$S$</span> to <span class="math-container">$T$</span> for <span class="math-container">$S,T \in V$</span>. If <span class="math-container">$G$</span> includes a cycle, how can I find a route that includes <span class="math-container">$n$</span> iterations of the cycle before following along an alternate edge?</p>
<p>For instance, let's assume I have the following cyclic graph: <span class="math-container">$\{(S,A), (A,B), (B,S), (B,T)\}$</span> with some arbitrary weights.
<a href="https://i.sstatic.net/f5uYcfh6.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/f5uYcfh6.png" alt="Cyclic graph with 4 nodes." /></a></p>
<p>Running Djikstra's from <span class="math-container">$S$</span> to <span class="math-container">$T$</span> would give the following path: <span class="math-container">$S \rightarrow A \rightarrow B \rightarrow T$</span>. But what if the edge <span class="math-container">$(B,T)$</span> depends on the number of cycles traversed in the given path? This is solvable by forming a new DAG that explicitly breaks the cycle, for instance if <span class="math-container">$(B, T)$</span> exists only after <span class="math-container">$n=2$</span> iterations of the cycle, then the path can be written as: <span class="math-container">$R = \{(S,A_0), (A_0, B_0), (B_0, S_1), (S_1, A_1), (A_1, B_1), (B_1, S_2), (S_2, A_2), (A_2, B_2), (B_2, T) \}$</span></p>
<p><a href="https://i.sstatic.net/fzWf5VB6.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/fzWf5VB6.png" alt="Cyclic graph broken into a longer DAG with 10 nodes." /></a></p>
<p>Is there a way to modify a route-finding algorithm such that it treats the edge <span class="math-container">$(B, T)$</span> conditionally, based on the number of cycles of the graph the route has processed through? Or in order to specify such an edge do I have to break down the cycles into this far larger DAG?</p>

<graph-theory><graph-algorithms>
Escaping the cycle: Route planning in graphs with conditional logic
Fifteen12
# Escaping the cycle: Route planning in graphs with conditional logic

(Asked by: username_0 on 2024-08-15)

Given a directed graph $G(V, E)$, I want to find a route, $R \in E^\*$ from $S$ to $T$ for $S,T \in V$. If $G$ includes a cycle, how can I find a route that includes $n$ iterations of the cycle before following along an alternate edge?

For instance, let's assume I have the following cyclic graph: $\{(S,A), (A,B), (B,S), (B,T)\}$ with some arbitrary weights.
[![Cyclic graph with 4 nodes.](https://i.sstatic.net/f5uYcfh6.png)](https://i.sstatic.net/f5uYcfh6.png)

Running Djikstra's from $S$ to $T$ would give the following path: $S \rightarrow A \rightarrow B \rightarrow T$. But what if the edge $(B,T)$ depends on the number of cycles traversed in the given path? This is solvable by forming a new DAG that explicitly breaks the cycle, for instance if $(B, T)$ exists only after $n=2$ iterations of the cycle, then the path can be written as: $R = \{(S,A\_0), (A\_0, B\_0), (B\_0, S\_1), (S\_1, A\_1), (A\_1, B\_1), (B\_1, S\_2), (S\_2, A\_2), (A\_2, B\_2), (B\_2, T) \}$

[![Cyclic graph broken into a longer DAG with 10 nodes.](https://i.sstatic.net/fzWf5VB6.png)](https://i.sstatic.net/fzWf5VB6.png)

Is there a way to modify a route-finding algorithm such that it treats the edge $(B, T)$ conditionally, based on the number of cycles of the graph the route has processed through? Or in order to specify such an edge do I have to break down the cycles into this far larger DAG?

**Tags:** graph-theory, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2024-08-26. Score: 2 | Accepted answer

First, let's define/simplify the situation or condition.

We have a graph with vertices and edges.
Some edges are special, they open up (get activated) only after waiting for some time at the source.

This waiting time is spent by taking a cycle tour.
Start from the current node, follow some other edges (hopefully normal edges), and finally reach back to the current node. Now check whether the special edge has opened up else take the cycle again.

The exact number of cycles required to activate each special edge is known (specified).

**The problem is to find the shortest path from a source to a destination vertex in this graph.**

Let's see how to solve this problem using an example.

[![Example](https://i.sstatic.net/MUuiCYpB.png)](https://i.sstatic.net/MUuiCYpB.png)

We have a graph G with

6 vertices (A, B, C, D, E, F)

6 normal edges (source, destination, cost)

1 special edge (source, destination, cost, number of cycles to activate it)

The goal is to find the shortest path (and cost) from A to E.

B-E is the special edge. But to activate it, we have to visit B, 2 times. Before taking B-E,
we have to traverse (B-C-D-B) 2 times. This cycle path can be determined by finding the shortest path from B to B (assuming no self-loops in the graph).

For each special edge's source vertex, calculate (and save) the cycle path and cost of taking that cycle path for the required number of times (waiting cost).

Now we can convert the special edges to normal edges by adding the calculated waiting cost to the original cost of that edge.

Original cost of B-E is 1.
Cost of cycle B-C-D-B is 3.
Taking this cycle for 2 times will give total waiting cost as 3\*2=6.
The updated cost of B-E is 1 + 6 = 7.

Now this graph becomes a normal graph (but there is a catch).

[![temporary graph](https://i.sstatic.net/KyWgp4Gy.png)](https://i.sstatic.net/KyWgp4Gy.png)

Find shortest path from A to E on this graph.
You get A-B-E, the cost is 1 + 7 = 8.

The cost is final, but the actual path must include cycle path also.

Replace each special edge with its cycle path (which we have already computed) repeated given number of times to activate the edge

A-**B-E** becomes A-**B-C-D-B-C-D-B-E**

This answer may not be a complete solution but may work as a good starting point.


---

