Finding Shortest Paths in the Real World

CSE Teaching Faculty Candidate Seminar

Zoom link for remote participants

Abstract:  In our previous class, we studied Dijkstra’s algorithm for computing shortest paths in graphs. Today we will study the A* algorithm, the most widely-used algorithm in practice. The A* algorithm is mostly the same as Dijkstra’s algorithm, with one tiny difference: the algorithm has access to some additional information about the graph. For this reason, A* is an “informed search algorithm”. Later we might also see how these ideas could be extended to even more general settings.

Bio: Kshitij Gajjar did his PhD from TIFR, India, and followed that up with two stints as a postdoc and a faculty position at IIT Jodhpur. He is presently an assistant professor at IIIT Hyderabad.