Netowrk "Routing" Algorithm

[tomercagan]

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

[Zachm]

1. What shortest path algorithm will work for me (saving the path itself and not results only)

Dijkstra's Algorithm or A* algorithm.
Note that Dijkstra's method will ensure exact results while A* is not as precise but will run much faster.

2. Is there a better approach to solve this problem?

Your approach seems perfectly fine to me .

Regards,

Zachm

[tomercagan]

Hi Zachm,

Thanks for the input!

To your experience, by how much would the A* be fater the Dijkstra's? Would anyone be fast enough to search a few 1000s node's graph in a matter of seconds?

Thanks again,

Tomer

< I asked also this but remove it after re-reading the algorithm implementation. (If anyone wonder about this, it is simple to solve by keeping the next hop pointer as we go through the algorithm)
Do I have to do special "version" in order to save the path in either of the algorithms?>