Hi,

I have a task at work relating finding the two shortest paths with enough capacity between two nodes in a network. The two paths can not contain the same nodes.

The distance between connected nodes is always 1 (so a binary representation maybe more appropriate for the search).

I need to be able to know the nodes in the path (to establish a route).

From school I remember that one of the shortest path algorithms also give you the actual nodes in the path.

A simple appraoch I thought of (which is not necessarily efficient):
The data I have:
Nodes connectivity (graph)
Link Capacity (note - not distance!)

Find two paths from source (i) to sink (j) with capacity C

Solution:
1. Remove all links with not enough capacity
2. Run shortest path algorithm to find the path with enough capacity
3. Remove all nodes used in path found in step two
4. Re-run the algorithm to find alternative path

As I said before, this is not very efficient but the only solution I could think of...

My questions:
1. What shortest path algorithm will work for me (saving the path itself and not results only)
2. Is there a better approach to solve this problem?

Any input will be great!

Thanks

Tomer