Using a road network, we were given the task to find the shortest path using various algorithms for each team, and our team was given the Edmonds–Karp algorithm to implement it.

But reading the definition, I'm struggling to see what the capacity and flow would be in a road network.

Originally I thought a good candidate for the capacity would be the speed limit for each street/edge, but then because speed doesn't increase because two streets converge, so the flow would not make sense in that interpretation.

Then maybe the number of cars in any given time could be the flow, and the maximum number of cars for a street (length of road/length of average car) could be the capacity, but I don't see how would the maximum flow in this case point to a path.

So my question is, is there a way to specialize the max flow problem to find the shortest path in a weighted, directed graph?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.