I have a directed weighted graph with cycles (example graph).
My goal is to get the maximum path from vertex "St" to vertex "E1".
Without that positive cycles I can use the Bellman Ford algorithm with negative weights at the edges to find the longest path. But because of the positive cycle, the longest path is ∞.
Additionally I have probabilities on the edges which I can use to create the path:
In each run of the cycle (e.g. st -> z3 -> z2) I have a 20% probabilty of going st -> z3. This means, in the second run I have 20% of 20% = 4% probability, in the third run I have 0.8% probability and so on. I can define an abort criterion which stops using the edge if the probability is below a specific value.
My question is now: Is there a generic algorithm to solve my problem to get the expected longest path? I'm not that familiar with all the algorithms and thus its hard to find something related.
I read an article in a book, which says, I have to "extract" the cycle in the graph to transform it to a directed acyclic graph. Extract means, I have to add as many iterations of the cycle to the graph as I need (e.g. to come to a probability < 0.1%).
Is this the right approach or do you have any other ideas?
Best Answer
The graph you describe is in fact a Markov chain. What you are looking for is the expected value of the path for $St$ to $E1$. Notice that there is no notion of maximum value, since there are no choice to make, all the choices are made by the probability on the edges
In Markov chain, you can actually compute this value as the solution of the following equations:
Let $Trap(E1)$ be the set of nodes from which $E1$ is not accessible For any node $n$ define the variable $x_n$ that represent the expect value of the path from $n$ to $E_1$.
If $n\in Trap(E)$ then add the equation $x_n=0$.
More over $x_{E1}=0$
For all node $n\in N\setminus Trap(E1)$ add the equation: $$ x_n = \sum_{n'\in N\setminus Trap(E1)} p(n,n')(w(n,n')+x_{n'})$$ where $p(n,n')$ denotes the probability to take an edge form $n$ to $n'$ and $w(n,n')$ the weight of this edge.
You have $|N|$ variables and $|N|$ equations thus an unique solution.
the value you are looking for is $x_{St}$
On your example it gives: $$x_{St}=0.8(1+x_{z_1})+0.2(x_{z_3}+1)$$ $$x_{z_3}=0.6(1+x_{z_2})$$ $$x_{z_2}=0.1(3+x_{St})+0.5(x_{z_4}+3)+0.1(x_{E1}+3)$$ $$x_{Z_1}=0.75(1+x_{z_2})+0.5(x_{z_4}+1)$$ $$x_{z_4}=4+x_{E_1}$$
And I let you solve it by elimination of variables for example.