432 problem of searching a maximum number of edge-disjoint shortest paths |
432 problem of searching a maximum number of edge-disjoint shortest paths |
433 between |
433 between |
434 two nodes \c s and \c t. Shortest here means being shortest w.r.t. |
434 two nodes \c s and \c t. Shortest here means being shortest w.r.t. |
435 non-negative edge-lengths. Note that |
435 non-negative edge-lengths. Note that |
436 the comprehension of the presented solution |
436 the comprehension of the presented solution |
437 need's some knowledge from elementary combinatorial optimization. |
437 need's some elementary knowledge from combinatorial optimization. |
438 |
438 |
439 If a single shortest path is to be |
439 If a single shortest path is to be |
440 searched between two nodes \c s and \c t, then this can be done easily by |
440 searched between \c s and \c t, then this can be done easily by |
441 applying the Dijkstra algorithm class. What happens, if a maximum number of |
441 applying the Dijkstra algorithm. What happens, if a maximum number of |
442 edge-disjoint shortest paths is to be computed. It can be proved that an |
442 edge-disjoint shortest paths is to be computed. It can be proved that an |
443 edge can be in a shortest path if and only if it is tight with respect to |
443 edge can be in a shortest path if and only if it is tight with respect to |
444 the potential function computed by Dijkstra. Moreover, any path containing |
444 the potential function computed by Dijkstra. Moreover, any path containing |
445 only such edges is a shortest one. Thus we have to compute a maximum number |
445 only such edges is a shortest one. Thus we have to compute a maximum number |
446 of edge-disjoint paths between \c s and \c t in the graph which has edge-set |
446 of edge-disjoint paths between \c s and \c t in the graph which has edge-set |
921 /// everywhere true. We note that for sake of efficiency, |
921 /// everywhere true. We note that for sake of efficiency, |
922 /// \c RevGraphWrapper is implemented in a different way. |
922 /// \c RevGraphWrapper is implemented in a different way. |
923 /// But BidirGraphWrapper is obtained from |
923 /// But BidirGraphWrapper is obtained from |
924 /// SubBidirGraphWrapper by considering everywhere true |
924 /// SubBidirGraphWrapper by considering everywhere true |
925 /// valued maps both for forward_filter and backward_filter. |
925 /// valued maps both for forward_filter and backward_filter. |
926 /// Finally, one of the most important applications of SubBidirGraphWrapper |
926 /// |
|
927 /// The most important application of SubBidirGraphWrapper |
927 /// is ResGraphWrapper, which stands for the residual graph in directed |
928 /// is ResGraphWrapper, which stands for the residual graph in directed |
928 /// flow and circulation problems. |
929 /// flow and circulation problems. |
929 /// As wrappers usually, the SubBidirGraphWrapper implements the |
930 /// As wrappers usually, the SubBidirGraphWrapper implements the |
930 /// above mentioned graph structure without its physical storage, |
931 /// above mentioned graph structure without its physical storage, |
931 /// that is the whole stuff is stored in constant memory. |
932 /// that is the whole stuff is stored in constant memory. |