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?