The Shortest Path Problem

Often people shouldn’t reinvent the wheel, however in my learning at Hacker School I feel that for certain areas it is likely important to try and think up a solution for a well known (and most likely solved) problem and see what you come up with.

Today, I was thinking of a problem that would appear in a possible project that Sitong suggested. The project involved creating a type of “heat” map which would represent the minutes to a destination given walking and public transportation options. In mulling over this in my head it presented one of the classic problems in algorithms… the shortest path problem. I have little experience with algorithms so I thought this would be a great problem to come up with a personal solution before checking for the optimal solution. Hopefully my solution will turn out to be the optimal.

In this problem, you are given a graph with nodes and connections with values, in this case the values for the connections represent minutes of travel between each node. The nodes will represent travel options between two points on a map and the goal is to find the shortest path from an initial starting node and a chosen end node.

In my haze of sleep I began to think of solutions for a quick optimization of finding the shortest path and began to envision the graph node network as a net that is malleable. If one picks the starting node and ending node in each hand and stretches, the shortest path will appear as it will be the first path that can no longer stretch between the two hands (ignoring of course all physical tangling of the net). The problem I face is to quickly calculate the distance from every node on a map to another node, and if this act of “lifting” up the node from the net instantly reveals the shortest node it may be somehow translatable in code.

My currently train of thought brings me to trees. Given a graph network, it may be possible to translate that graph into a tree and stretch it out until you find the shortest path between the two nodes…

~ Hacking in Progress 😛 ~

After doing some reading and implementing Dijkstra’s algorithm in Ruby, I see the parallels of my visual thoughts and the mathematical explanations. Creating a even set of sub-nodes and traveling down all parallel paths until you hit nodes is analogous to lifting a net and having all connections lift off a table until node by node the solution appears. I find this connection between my thoughts and the derivation fascinating and really do wonder if there are other things out there that I could find novel solutions to. Looking forward to more late-night epiphanies and other sparks of inspiration!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

<span>%d</span> bloggers like this: