doc/min_cost_flow.dox
changeset 874 d8ea85825e02
parent 755 134852d7fb0a
parent 786 e20173729589
child 877 141f9c0db4a3
equal deleted inserted replaced
1:c4104acc14db 3:d69f1d82f728
    76  - For all \f$uv\in A\f$ arcs:
    76  - For all \f$uv\in A\f$ arcs:
    77    - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
    77    - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
    78    - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
    78    - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
    79    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
    79    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
    80  - For all \f$u\in V\f$ nodes:
    80  - For all \f$u\in V\f$ nodes:
    81    - \f$\pi(u)<=0\f$;
    81    - \f$\pi(u)\leq 0\f$;
    82    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
    82    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
    83      then \f$\pi(u)=0\f$.
    83      then \f$\pi(u)=0\f$.
    84  
    84  
    85 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
    85 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
    86 \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
    86 \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
   143  - For all \f$uv\in A\f$ arcs:
   143  - For all \f$uv\in A\f$ arcs:
   144    - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
   144    - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
   145    - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
   145    - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
   146    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
   146    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
   147  - For all \f$u\in V\f$ nodes:
   147  - For all \f$u\in V\f$ nodes:
   148    - \f$\pi(u)>=0\f$;
   148    - \f$\pi(u)\geq 0\f$;
   149    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
   149    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
   150      then \f$\pi(u)=0\f$.
   150      then \f$\pi(u)=0\f$.
   151 
   151 
   152 */
   152 */
   153 }
   153 }