A maximum bottle neck (s-t) path usually refers to a path from s to t that maximizes the capacity of the edge with the smallest capacity on the path (a quick google search could have told you that as well en.wikipedia.org/wiki/Widest_path_problem)

The ambiguity lies in the fact that a certain flow can be decomposed into paths in many different ways and some of these decompositions may meet you requirements and other may not, although they represent the same flow. From your question it is not clear if you want all of the possible decompositions to be paths of length three or if the existence of one such decomposition is enough. Apparently you were looking for the later one. But this was not explicitly stated in the question.

It is more tricky because even if you know the optimal number of refills from some node u to another node v and the optimal number of refills from v to a third node w, you don't automatically know how many refills are necessary to go from u to w via v. You can not just add them up since it is not clear weather a refill is necessary at v. Thus, I don't see a straight forward modification of the Floyd-Warshall algorithm.

Well, first of all I am glad that the problem is solved. However, as I see it, D.W. did not try to answer your question but help you restate the problem in a more precise manner. And he also has a valid point in doing so. For instance, if you consider the graph from the example I gave above, there is another max flow that satisfies your constraint, namely s->u->v->t and s->v->x->t. But we can also express this flow as s->u->v->x->t and s->v->t, which would not satisfy your requirement. Do you see the ambiguity now?

Even if refills are possible at every node, I don't think the Floyd-Warshall algorithm is straight forward to use. If it is, I would be interested in seeing how this can be done.

That dosn't answer my question of what you mean by "use". If you mean that there is flow entering and exiting a vertex via different edges, then the same thing is possible in the original graph. For instance, consider the Graph G = ({s,t,u,v,w,x}, {(u,v),(w,v),(v,x)} U {"source and sink edges"}). A maximum flow that satisfies your additional constraint (which is not clearly stated at all as D.W. pointed out), would be a path s->u->v->t and another path s->w->v->x->t. Note that v was "used" twice in this maximum flow. Please be more specific. Otherwise it is impossible to help.

What do you mean by a vertex is used at most once? I don't understand your point. Maybe you can give an example. Also, maybe I should clarify that the capacities of the edges in G' correspond to their counterparts in G, except for (v'',v'), which has no corresponding edge in G.

Although I agree that the Floyd-Warshall algorithm is not useful here, I don't think the task at hand is NP-hard. Using Dijkstra's algorithm to compute the minimal number of refills for any ordered pair of vertices should work fine. Just use the number of refills and the remaining fuel in this lexicographic order as distance measure.

This depends on what you mean by very large integers. Could you be more specific?