Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm facing with the following problem.

Suppose to have a generic oriented graph with curl (there can be an edge from a node to itself). Suppose also that you have to perform a $n$-vertices-long path around the graph starting from a given vertex $S$. When one goes from the node $i$ to the node $j$ , then a cost function is updated accordingly to the movement.
In particular, let $c_0$ be a given initial cost. When one perform a movement, say we move from the vertex $S$ to the vertex $j$, then he can calculate $c_1$ with a certain function $$ c_1 = f(c_0, \theta_j)$$ where $\theta_j$ is a parameter attached to the node $j$. After this, he can move from node $j$ to node $k$ and then he will have $$ c_2 = f(c_1, \theta_k)$$ and so on. If $i(t)$ is the vertex visited at time $t$ then we have that: $$ c_t = f(c_{t-1}, \theta_{i(t)})$$ Finally, after $n$ steps, we have my $c_n$, which obviously depends on the particular path we followed.

My question is: is there some algorithm/theory about how to compute the path which guarantees that $c_n$ is the lowest (or the greatest)?

share|improve this question
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.