## 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 = {}
for c in cons:```
`cS = c.split(" ")`
`if cS not in nodeNames:`
`nodeNames.append(cS)`
`nodeConnect[cS] = []`
`if cS not in nodeNames:`
`nodeNames.append(cS)`
`nodeConnect[cS] = []`
`if cS != cS:`
`nodeConnect[cS].append(cS)`
`nodeConnect[cS].append(cS)`
`nodeWeights[cS + ">" + cS] = int(cS)`
```nodeWeights[cS + ">" + cs] = int(cS)
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).