UXsim
UXsim copied to clipboard
Speed up `route_search_all` by using priority queue optimized Dijkstra's
After some benchmarks, I discovered the route_search_all
takes up a majority (~80% of runtime) in my simulation. This feature request proposes optimizing the route search algorithm, specifically by replacing the current implementation with a more efficient algorithm suited for sparse graphs that are often encountered in real-world road networks.
Issue:
The Floyd-Warshall algorithm, while comprehensive in determining the shortest distances between all pairs of vertices, does not inherently provide the immediate next step in the shortest path from one node to another. The manual computation of this next
matrix, especially in a graph of this scale and sparsity, is inefficient and time-consuming, as indicated by execution timings: next matrix computed in 19.861 sec
.
https://github.com/toruseo/UXsim/blob/584b5d7842e92441a3734b39e46c42408e8268c6/uxsim/uxsim.py#L992-L999
Proposed Solution: Adopt Dijkstra's algorithm, with a priority queue, for the computation of shortest paths. Dijkstra's algorithm is more suited to sparse graphs and inherently provides the immediate next node on the shortest path as part of its output, thus eliminating the need for the currently cumbersome post-processing step.
Technical Justification:
- Efficiency in Sparse Graphs: Dijkstra's algorithm scales better with sparse graphs, operating at (O((V + E) \log V)) complexity, where (V) is the number of vertices and (E) is the number of edges. This is a significant improvement over the Floyd-Warshall’s (O(V^3)) complexity, making Dijkstra's algorithm particularly suitable for our graph's sparse nature.
- Direct Path Reconstruction: Unlike Floyd-Warshall, Dijkstra’s algorithm directly provides the next node in the shortest path from the source to every other node. This feature simplifies the routing module by eliminating the need for additional calculations to determine the next steps in paths.
- Optimization Potential: Shifting to Dijkstra's algorithm with a priority queue not only addresses the current bottleneck but also opens up opportunities for further optimizations, including potentially leveraging parallel computations for running Dijkstra's from multiple sources simultaneously.