Skip to main content



Algorithmically Determining the Shortest Path Between 2 Nodes

The ability for edges to contain values is an extremely important aspect of graph theory. For example, in a network representing a subway system, a weighted edge connecting two nodes could mean the distance between the stations those nodes represent. A weighted edge between two nodes in a social network could mean the strength of the tie between those two individuals, where a smaller number means a stronger tie for example. From these examples given, we see the ability to find the shortest path between any two given nodes can be invaluable: it could mean minimizing the time or monetary costs of subway travel, or accurate recommendations for potential friends for a social platform. For a small enough network, one can simply observe the graph, figure out a few different paths and the “costs” associated, and determine an optimal path, but what if the network consists of millions of nodes and edges? How do we utilize computers for this task? I’ll provide a brief overview of Dijkstra’s Algorithm, a simple greedy shortest path algorithm.

Say we start at an initial node A and want to get to Z. First, we’ll consider all nodes connected directly to A via an edge, and assign each one of those nodes a “tentative distance” value equal to the weight of that edge. Basically, the idea of each node’s tentative distance value is the shortest path distance from A to that node, given all the nodes and edges we’ve considered so far. So in the first step, since there’s only 1 edge connecting each of A’s neighbors to A, it makes sense that the tentative distance of each of A’s neighbors are equivalent to their respective edges. Now that we’re done with A, we’ll go ahead and do the same with each of A’s neighbors. For example, for A’s first neighbor (let’s call it A’), we’ll look at each one of its neighbors that aren’t A, and for each, we compute the tentative distance by adding the tentative distance of A’ to the distance of the edge linking A’ and its neighbor. Now, there might be a situation where a neighbor of A’ already has a tentative distance – we’ll replace it with the new tentative distance if it’s smaller. Now we do the same thing with A”, the 2nd neighbor of A, and we won’t consider A or A’ since we’ve already been through them, and so on – basically, whenever we’ve examined all the edges of a node, we’ll mark that node as “visited”, meaning we won’t ever examine it again.

Assuming the graph is connected, this algorithm will eventually reach every single node given enough iterations. However, we can end it after B is marked as “visited”. The shortest path at this point is simply the series of nodes and edges from A to B with a distance equal to B’s tentative distance.

http://motherboard.vice.com/read/the-simple-elegant-algorithm-that-makes-google-maps-possible

Comments

Leave a Reply

Blogging Calendar

September 2015
M T W T F S S
 123456
78910111213
14151617181920
21222324252627
282930  

Archives