O'Reilly logo

Python Algorithms: Mastering Basic Algorithms in the Python Language by Magnus Lie Hetland

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 9. From A to B with Edsger and Friends

 

The shortest distance between two points is under construction.

 
 --Noelie Altito

It's time to return to the second problem from the introduction:[123] how do you find the shortest route from Kashgar to Ningbo? If you pose this problem to any map software, you'd probably get the answer in less than a second. By now, this probably seems less mysterious than it (maybe) did initially, and you even have tools that could help you write such a program. You know that BFS would find the shortest path if all stretches of road had the same length, and you could use the DAG shortest path algorithm as long as you didn't have any cycles in your graph. Sadly, the road map of China contains both cycles and roads ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required