444 edge can be in a shortest path if and only if it is tight with respect to |
444 edge can be in a shortest path if and only if it is tight with respect to |
445 the potential function computed by Dijkstra. Moreover, any path containing |
445 the potential function computed by Dijkstra. Moreover, any path containing |
446 only such edges is a shortest one. Thus we have to compute a maximum number |
446 only such edges is a shortest one. Thus we have to compute a maximum number |
447 of edge-disjoint paths between \c s and \c t in the graph which has edge-set |
447 of edge-disjoint paths between \c s and \c t in the graph which has edge-set |
448 all the tight edges. The computation will be demonstrated on the following |
448 all the tight edges. The computation will be demonstrated on the following |
449 graph, which is read from a dimacs file. |
449 graph, which is read from the dimacs file \ref sub_graph_adaptor_demo.dim. |
450 |
450 The full source code is available in \ref sub_graph_adaptor_demo.cc. |
|
451 If you are interested in more demo programs, you can use |
|
452 \ref dim_to_dot.cc to generate .dot files from dimacs files. |
|
453 The .dot file of the following figure of was generated generated by |
|
454 the demo program \ref dim_to_dot.cc. |
|
455 |
451 \dot |
456 \dot |
452 digraph lemon_dot_example { |
457 digraph lemon_dot_example { |
453 node [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; |
458 node [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; |
454 n0 [ label="0 (s)" ]; |
459 n0 [ label="0 (s)" ]; |
455 n1 [ label="1" ]; |
460 n1 [ label="1" ]; |