- void initialize_work_lengths();
- void update_work_lengths();
- void force_positive_work_lengths();
- void find_shortest_path(Vertex **front, Vertex **new_front);
+ // Set the distance_from_source fields to the number of DP
+ // iterations needed to update it. Abort if the graph is not a DAG.
+ void compute_dp_ranks();
+
+ // Uses the estimated vertex distances to the source to make all the
+ // edge lengths positive, resulting in an identical added value to
+ // all the paths from the same initial node to the same final node
+ // (in particular from source to sink)
+ void update_positivized_lengths();
+
+ // It may happen that numerical errors in update_positivized_lengths
+ // make the resulting lengths negative, albeit very small. The
+ // following method forces all negative lengths to zero, and prints
+ // the total correction when compiled in VERBOSE mode.
+ void force_positivized_lengths();
+
+ // Visit the vertices according to _dp_order and update their
+ // distance from the source
+ void dp_compute_distances();
+
+ // Set in every vertex pred_edge_toward_source correspondingly to
+ // the path of shortest length. The current implementation is
+ // Dijkstra with a Binary Heap (and not with Fibonnaci heap (yet))
+ void find_shortest_path();
+
+ // Follows the path starting on edge e and returns the number of
+ // nodes to reach the sink. If path is non-null, stores in it the
+ // nodes met along the path, and computes path->length properly.
+ int retrieve_one_path(Edge *e, Path *path);