+void MTPGraph::dp_distance_propagation() {
+ Vertex *v, *tv;
+ Edge *e;
+ scalar_t d;
+
+ for(int k = 0; k < _nb_vertices; k++) {
+ _vertices[k].distance_from_source = FLT_MAX;
+ _vertices[k].pred_edge_toward_source = 0;
+ }
+
+ _source->distance_from_source = 0;
+
+ for(int k = 0; k < _nb_vertices; k++) {
+ v = _dp_order[k];
+ for(e = v->leaving_edges; e; e = e->next_leaving_edge) {
+ d = v->distance_from_source + e->positivized_length;
+ tv = e->terminal_vertex;
+ if(d < tv->distance_from_source) {
+ tv->distance_from_source = d;
+ tv->pred_edge_toward_source = e;
+ decrease_distance_in_heap(tv);
+ }
+ }
+ }
+
+#ifdef DEBUG
+ for(int k = 0; k < _nb_vertices; k++) {
+ if(_vertices[k].distance_from_source == FLT_MAX) abort();
+ }
+#endif
+}
+
+// This method does not change the edge occupation. It only set
+// properly, for every vertex, the fields distance_from_source and
+// pred_edge_toward_source.
+
+void MTPGraph::find_shortest_path() {
+ Vertex *v, *tv;
+ Edge *e;
+ scalar_t d;
+
+#ifdef DEBUG
+ if(is_dag()) {
+ cout << "find_shortest_path: DAG -> ok" << endl;
+ } else {
+ for(int e = 0; e < _nb_edges; e++) {
+ if(_edges[e].positivized_length < 0) abort();
+ }
+ cout << "find_shortest_path: All positivized_length are positive -> ok" << endl;
+ }
+#endif
+
+ for(int k = 0; k < _nb_vertices; k++) {
+ _vertices[k].distance_from_source = FLT_MAX;
+ _vertices[k].pred_edge_toward_source = 0;
+ }
+
+ _heap_size = _nb_vertices;
+ _source->distance_from_source = 0;
+ decrease_distance_in_heap(_source);
+
+ do {
+#ifdef DEBUG
+ for(int k = 0; k < _heap_size; k++) {
+ if(_heap[0]->distance_from_source > _heap[k]->distance_from_source) abort();
+ }
+ // cout << "OK!" << endl;
+#endif
+
+ v = _heap[0];
+ _heap_size--;
+ Vertex **a = _heap, **b = _heap + _heap_size;
+ swap(*a, *b); swap((*a)->heap_position, (*b)->heap_position);
+ increase_distance_in_heap(_heap[0]);
+
+ for(e = v->leaving_edges; e; e = e->next_leaving_edge) {
+ d = v->distance_from_source + e->positivized_length;
+ tv = e->terminal_vertex;
+ if(d < tv->distance_from_source) {
+ ASSERT(tv->heap_position - _heap < _heap_size);
+ tv->distance_from_source = d;
+ tv->pred_edge_toward_source = e;
+ decrease_distance_in_heap(tv);
+ }
+#ifdef DEBUG
+ for(int k = 0; k < _heap_size; k++) {
+ if(_heap[0]->distance_from_source > _heap[k]->distance_from_source) abort();
+ }
+#endif
+ }
+ } while(_heap_size > 0);
+
+#ifdef DEBUG
+ for(int k = 0; k < _nb_vertices; k++) {
+ v = &_vertices[k];
+ for(e = v->leaving_edges; e; e = e->next_leaving_edge) {
+ d = v->distance_from_source + e->positivized_length;
+ tv = e->terminal_vertex;
+ if(d < tv->distance_from_source) abort();
+ }
+ }
+#endif
+ cout << "DONE!" << endl;
+}
+
+void MTPGraph::find_best_paths(scalar_t *lengths) {