equal
deleted
inserted
replaced
132 Path q; |
132 Path q; |
133 Path r; |
133 Path r; |
134 { |
134 { |
135 Dijkstra<Graph,CM> dij(_g,_cost); |
135 Dijkstra<Graph,CM> dij(_g,_cost); |
136 dij.run(s,t); |
136 dij.run(s,t); |
137 cnt++; |
|
138 if(!dij.reached(t)) return Path(); |
137 if(!dij.reached(t)) return Path(); |
139 p=dij.path(t); |
138 p=dij.path(t); |
140 cp=cost(p); |
139 cp=cost(p); |
141 dp=delay(p); |
140 dp=delay(p); |
142 } |
141 } |
143 if(delay(p)<=delta) return p; |
142 if(delay(p)<=delta) return p; |
144 { |
143 { |
145 Dijkstra<Graph,DM> dij(_g,_delay); |
144 Dijkstra<Graph,DM> dij(_g,_delay); |
146 dij.run(s,t); |
145 dij.run(s,t); |
147 cnt++; |
|
148 q=dij.path(t); |
146 q=dij.path(t); |
149 cq=cost(q); |
147 cq=cost(q); |
150 dq=delay(q); |
148 dq=delay(q); |
151 } |
149 } |
152 if(delay(q)>delta) return Path(); |
150 if(delay(q)>delta) return Path(); |
153 while (true) { |
151 while (true) { |
154 lambda=(cp-cq)/(dq-dp); |
152 lambda=(cp-cq)/(dq-dp); |
155 _co_map.lambda(lambda); |
153 _co_map.lambda(lambda); |
156 _dij.run(s,t); |
154 _dij.run(s,t); |
157 cnt++; |
|
158 r=_dij.path(t); |
155 r=_dij.path(t); |
159 cr=cost(r); |
156 cr=cost(r); |
160 dr=delay(r); |
157 dr=delay(r); |
161 if(!tol.less(cr+lambda*dr,cp+lambda*dp)) { |
158 if(!tol.less(cr+lambda*dr,cp+lambda*dp)) { |
162 lo_bo=cq+lambda*(dq-delta); |
159 lo_bo=cq+lambda*(dq-delta); |