Saturday, 31 August 2013

Finding path with maximum capacity in graph

Finding path with maximum capacity in graph

I am helping a friend with a work related project where, he needs to
calculate the maximum capacity from a node a to a node b, where the edge
has a capacity. However the maximum capacity in a path from a to b is
limited by the edge with the lowest capacity.
Let me try to explain with a simple sample
So the graph is a directed graph with weighted edges, and it can be
cyclic. The path with the highest capacity would be s->b->t and have the
capacity of 250, since that edge is setting the limit.
I have done a bit of reading and found out that this type of problem is a
"Widest path problem" or I would call it something like a path with
minimum maximum capacity, but I haven't found any examples or any pseudo
code explaining how to tackle this.
I was thinking something in the lines of finding all paths from s to t,
using BFS and somehow only to allow visiting a node once in a path, and
then find the minimum value in the path, would that work?

No comments:

Post a Comment