Trouble Understanding Shortest Path Tree Construction During Highway Building

[mark-idleman]

Hello,

I've worked fairly extensively with this algorithm for a large project while in college, and I only recently discovered this repository and have been reviewing the actual code. I'm a bit confused on one detail of the algorithm used to construct each highway, specifically line 267 of pruned _highway_labeling.h.

This line implies that if a vertex has already been included in a highway (and labels have already been constructed via a pruned Dijkstra's search from the highway), then during the construction of any subsequent shortest path trees (used to extract highways later in the algorithm), the vertex will not be considered during the normal Dijkstra's search used to build the shortest path tree. Is this intuition correct?

If so, doesn't this mean that the shortest path tree constructed during each regular Dijkstra's search (from which a new highway will be constructed) does not necessarily contain true shortest paths from the root to each leaf? If we essentially stop the Dijkstra's search early (and don't create a shortest path tree of the entire graph during each iteration of the loop on line 250), we're not considering certain (possibly shortest) paths that may include nodes already used in previously built highways, meaning that the highways we construct are not guaranteed to be shortest paths. This would be a problem from a theoretical standpoint, as the main proof of correctness presented in the paper relied on the fact that all highways represent true shortest paths in the graph.

Thank you, Mark

[kawatea]

Thank you for your comment.

That intuition is true, but it has no problem. We check current labels on line 277 and stop the search from the vertex if the distance is smaller than or equal to that calculated by them. If the vertex is already used as highways, the distance between this vertex and another vertex is calculated correctly. As a result, the highways we construct are shortest paths.

[mark-idleman]

Thank you very much for your quick reply! Ok, so to understand what you said correctly, if a vertex under consideration during the construction of the shortest path tree (what you called "w") has already been used in a highway, then necessarily the condition on line 277 will be true (ie, the labels already built for w and v return a distance less than or equal to the distance being considered for w), so you can catch this case early to prevent entering the if statement on line 268?

[kawatea]

That's true. The biggest reason I added this pruning is that checking current labels is a little time consuming. Therefore, preventing checking this condition helps us build labels faster.

[mark-idleman]

Ah, I see why that was included given that you were pruning during the construction of the shortest path tree.

I'm still a bit worried that pruning the shortest path tree at all can lead to root-to-leaf paths in the shortest path tree that are not true shortest paths; couldn't it be the case that the tree was pruned at some vertex u, and then the highway that was extracted during that iteration of the label building phase was the path in the shortest path tree from the root of the tree (let's call it s) to some other vertex v, but the true shortest path from s to v really traveled through u (and also included vertices that were not even considered, due to the fact that the search was pruned at u)? I'm essentially asking about the validity of a shortest path tree built using Dijkstra's when at least one leg of the search was cut short, but that leg of the search could have in fact modified (and improved upon) a different root-to-leaf path in the tree that was not pruned, and therefore could be extracted as a highway. How can you be sure that this is truly a valid shortest path?

[kawatea]

This is also checked on line 277. If the true shortest path from s to v is through u, current labels for s and v contain u (or some other vertices passed from s to v). Therefore such v is pruned and not pushed into the priority queue.

Actually the line 277 should be on line 267, but we want to reduce this check as I mentioned before. So we update the cost on line 270 also to reduce this check. This makes the code a bit confusing.

[mark-idleman]

Ok, that's making more sense to me now, thank you for the explanation! The construction of highways was one of the more confusing parts of the paper for me, and it would've been nice to have included more of these details in that section, but seeing the code makes the algorithm much clearer.

I thought the overall approach of the paper was very interesting, and it seems like there are a lot of areas where additional small improvements could be made. I'm looking forward to seeing where people take the original idea!