-void MTPGraph::find_best_paths(scalar_t *lengths, int *result_edge_occupation) {
- Vertex **front = new Vertex *[_nb_vertices];
- Vertex **new_front = new Vertex *[_nb_vertices];
+ _heap_size = _nb_vertices;
+ _source->distance_from_source = 0;
+ _source->decrease_distance_in_heap(_heap);
+
+ do {
+ // Get the closest to the source
+ v = _heap[0];
+
+ // Remove it from the heap (swap it with the last_slot in the heap, and
+ // update the distance of that one)
+ _heap_size--;
+ last_slot = _heap + _heap_size;
+ swap(*_heap, *last_slot); swap((*_heap)->heap_slot, (*last_slot)->heap_slot);
+ _heap[0]->increase_distance_in_heap(_heap, _heap + _heap_size);
+
+ // Now update the neighbors of the node currently closest to the
+ // source
+ 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_slot - _heap < _heap_size);
+ tv->distance_from_source = d;
+ tv->pred_edge_toward_source = e;
+ tv->decrease_distance_in_heap(_heap);
+ }
+ }
+ } while(_heap_size > 0);
+}