A new proof shows that an upgraded version of the 70-year-old Dijkstra’s algorithm reigns supreme: It finds the most efficient pathways through any graph.
It doesn’t just tell you the fastest route to one destination.
In an interview toward the end of his life, Dijkstra credited his algorithm’s enduring appeal in part to its unusual origin story. “Without pencil and paper you are almost forced to avoid all avoidable complexities,” he said.
Dijkstra’s algorithm doesn’t just tell you the fastest route to one destination. Instead, it gives you an ordered list of travel times from your current location to every other point that you might want to visit — a solution to what researchers call the single-source shortest-paths problem. The algorithm works in an abstracted road map called a graph: a network of interconnected points (called vertices) in which the links between vertices are labeled with numbers (called weights). These weights might represent the time required to traverse each road in a network, and they can change depending on traffic patterns. The larger a weight, the longer it takes to traverse that path.
To get a sense of Dijkstra’s algorithm, imagine yourself wandering through a graph, writing down the travel time from your starting point to each new vertex on a piece of scratch paper. Whenever you have a choice about which direction to explore next, head toward the closest vertex you haven’t visited yet. If you discover a faster route to any vertex, jot down the new time and cross out the old one. When you’re sure that you’ve found the fastest path, move the travel time from your notes to a separate, more presentable list.
Leave a reply