449 edge can be in a shortest path if and only if it is tight with respect to |
449 edge can be in a shortest path if and only if it is tight with respect to |
450 the potential function computed by Dijkstra. Moreover, any path containing |
450 the potential function computed by Dijkstra. Moreover, any path containing |
451 only such edges is a shortest one. Thus we have to compute a maximum number |
451 only such edges is a shortest one. Thus we have to compute a maximum number |
452 of edge-disjoint paths between \c s and \c t in the graph which has edge-set |
452 of edge-disjoint paths between \c s and \c t in the graph which has edge-set |
453 all the tight edges. The computation will be demonstrated on the following |
453 all the tight edges. The computation will be demonstrated on the following |
454 graph, which is read from the dimacs file \ref sub_graph_adaptor_demo.dim. |
454 graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim. |
455 The full source code is available in \ref sub_graph_adaptor_demo.cc. |
455 The full source code is available in \ref sub_graph_adaptor_demo.cc. |
456 If you are interested in more demo programs, you can use |
456 If you are interested in more demo programs, you can use |
457 \ref dim_to_dot.cc to generate .dot files from dimacs files. |
457 \ref dim_to_dot.cc to generate .dot files from dimacs files. |
458 The .dot file of the following figure of was generated generated by |
458 The .dot file of the following figure of was generated generated by |
459 the demo program \ref dim_to_dot.cc. |
459 the demo program \ref dim_to_dot.cc. |