free hit counter script

Tuesday, December 27, 2005

A Case of Dijkstra's (Not A Technical Post!)

E.W. Dijkstra, a brilliant scientist and a fine man, is credited for the invention of Dijkstra's Algorithm aka the shortest path algorithm. Dijkstra's algorithm is what's used behind the scenes to give us driving directions on mapquest or gps navigators. What's interesting about Dijkstra's algorithm, and is also the case with many computing algorithms, is that its applicable in our everyday life and not just technical problems. Let's look at this fun problem. It's really short and simple. So we are trying to find the shortest
path from node A to node D. The numbers on the edges between the nodes represent the distance.

A _3_B__4_ D
\_2__C__6_/

So we could go from A to D through B with a total cost of 7 or through C with a total cost of 8. In this simple problem obviously going through B leads shorter path. Although, and especially
in more complicated graphs, one might be inclined to go with C thinking that if C is closer to A than B that would yield a shorter path. And that's exactly what D's Algorithms proves wrong.

Dijkstra's Algorithm reminds me to focus on my long term goals. We do have choices that we make everyday and sometimes you have to pick the non ideal ones (short term wise) because it eventually leads to the shortest path to our end goals.