Programming and general geekiness.

Shortest route algorithm

A common (ish) problem in computing is identifying the lightest/quickest/shortest route across a graph or map. From the above graph we can clearly see that the fast route from A to G is ADG or ABDG however for some people it may be unclear how to identify this in an algorithm. Thankfully I spent all of yesterday evening writing up the following Python algorithm. It is relatively efficient however there are a few bugs that I am working on resolving. I’ve tried to do it in as few lines as possible:

nodeNames = []
nodeWeights = {}
nodeConnect = {}
cons = open(raw_input("Please enter a file name of the graph: ")).read().splitlines()
for c in cons:
cS = c.split(" ")
if cS[0] not in nodeNames:
nodeNames.append(cS[0])
nodeConnect[cS[0]] = []
if cS[1] not in nodeNames:
nodeNames.append(cS[1])
nodeConnect[cS[1]] = []
if cS[0] != cS[1]:
nodeConnect[cS[0]].append(cS[1])
nodeConnect[cS[1]].append(cS[0])
nodeWeights[cS[0] + ">" + cS[1]] = int(cS[2])
nodeWeights[cS[1] + ">" + cs[0]] = int(cS[2])
print "Graph loaded."
nodeStart, nodeEnd  = raw_input("Please enter location and destination: ").split(" ")
nodeSolved = {}
nodeSolvedRoute = {}
maxRoute = 1000000
for i in nodeNames:
nodeSolved[i] = maxRoute
nodeSolvedRoute[i] = ""
nodeSolved[nodeStart] = 0
nodeSolvedRoute[nodeStart] = nodeStart + ", "
options = []
examined = []
def evaluateLightest(current):
for connected in nodeConnect[current]:
if nodeSolvedRoute[current] + connected not in examined:
pathWeight = nodeSolved[current] + nodeWeights[current + ">" + connected]
examined.append(nodeSolvedRoute[current] + connected)
if pathWeight < nodeSolved[connected]:
nodeSolved[connected] = pathWeight
nodeSolvedRoute[connected] = nodeSolvedRoute[current] + connected + ", "
evaluateLightest(current)
evaluateLightest(nodeStart)
print nodeSolved[nodeEnd]
print nodeSolvedRoute[nodeEnd]

I think that it probably is possible to improve the algorithm and if I do I’ll update the source. The graph file should be as follows (for the above graph):

A B 2
A C 2
B D 1
B F 4
C D 2
C E 1
D F 1
D G 3
F G 3

For this example the program correctly outputs 6 and ABDG. I will make available a file I am working on with all of the London Tube Stations (and journey times).

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: