Everyone is welcome to attend the online N&O seminar with Willem Feijen (CWI). Title of his lecture: Using Machine Learning Predictions to Speed-up Dijkstra's Shortest Path Algorithm.
Abstract:
We study the use of machine learning techniques to solve a fundamental shortest path problem, where the goal is to compute a shortest path from a given source node to any of several designated target nodes. Basically, our idea is to combine a machine learning approach with an adapted version of Dijkstra's algorithm: Based on the trace of the algorithm, we use a neural network to predict the shortest path distance after only a few iterations.
Using this prediction, we can prune the search space explored by Dijkstra's algorithm which avoids a significant number of priority queue operations. Crucially, our approach always computes the exact shortest path distances and never uses more queue operations than the standard algorithm. We prove a lower bound on the number of queue operations saved by our new algorithm, which depends on the accuracy of the prediction. Our bound applies to arbitrary graphs as long as the edge weights are drawn at random. Our experimental findings on random instances confirm these bounds and show that the actual savings are oftentimes significantly higher.
Joint work with Guido Schäfer (CWI & UvA).
