Algorithms For Dummies

Defining what it means to  

find the shortest path

Many applications exist for shortest-route algorithms. The idea is to find the path 

that offers the smallest distance between point A and point B. Finding the shortest 

path is useful for both transportation (how to arrive at a destination consuming 

the least fuel) and communication (how to route information to allow it to arrive 

earlier). Nevertheless, unexpected applications of the shortest-path problem may 

also arise in image processing (for separating contours of images), gaming (how 

to achieve certain game goals using the fewest moves), and many other fields in 

which you can reduce the problem to an undirected or directed weighted graph.

The Dijkstra algorithm can solve the shortest-path problem and has found the 

most uses. Edsger W. Dijkstra, a Dutch computer scientist, devised the algorithm 

as a demonstration of the processing power of a new computer called ARMAC 

(

http://www-set.win.tue.nl/UnsungHeroes/machines/armac.html

)  in  1959. 

The algorithm initially solved the shortest distance between 64 cities in the 

Netherlands based on a simple graph map.

---

CHAPTER 9