Comparison of Shortest Path Algorithms
Posted: Mon Jul 08, 2024 4:25 pm
Hi there,
before I forget it: here's some fancy video playlist about different routing algorithms.
The videos apply different routing techniques and show the impact on performance, mainly driven by the size of the data structure that have been created during the algorithms process:
before I forget it: here's some fancy video playlist about different routing algorithms.
The videos apply different routing techniques and show the impact on performance, mainly driven by the size of the data structure that have been created during the algorithms process:
| Algorithm | Number of expanded nodes |
|---|---|
| Unidirectional Dijkstra | 468'113 nodes within 17'394ms |
| Unidirectionsl A-Star | 124'584 nodes within 5'366ms |
| Bidirectional Dijkstra | 183'438 nodes within 7'972ms |
| Bidirectional A-Star | 79'616 nodes within 4'087ms |
| Heuristic Bidirectional A-Star | 32'961 nodes within 1'809 ms |
- A unidirectional algorithm is slower than it's bidirectional version, but bidirectional one's aren't sufficient for a certain class of time dependent tasks (excat at start, exact at arrival, ...)