# Shortest path in a graph

Write a program to take a graph (from either standard input or a file, your choice) and find a shortest path in the graph.

Graphs are specified using the following format:

A---S   F--T
|  / \  |
| /   5 0
|/     \|
D----3--E

A-Z: nodes in the graph
-|/\: edges in the graph
0-9: weights on the edges
<space>: all the holes


All edges are undirected and lie along one of the 8 cardinal directions (i.e., no bends). Edges may optionally contain a weight from 0 to 9. The weight will not be on the last symbol that connects the edge to a node (i.e. edges need to have at least 3 symbols to contain a weight). Unweighted edges have a default weight of 1.

Your code should compute the shortest path between nodes S and T and print the length and the path, like this:

5:SDEFT


Shortest correct program wins.

• Does the graph diagram have to be parsed or can you use your own format? One example of a format - your graph could be represented as: AS0,SD0,SE5,DE3,FE0,FT0 (you could omit the commas if each entry is 3 bytes long.) – Thomas O Jan 28 '11 at 20:21
• Yes, you have to parse the graph as I specified. That's most of the problem, actually. The shortest path part just makes sure your parsing is correct. – Keith Randall Jan 28 '11 at 20:26
• The input format is really far too complicated and imho doesn't really add that much to the problem. – JPvdMerwe Jan 28 '11 at 23:32
• Just thought folks here would like to try something a bit more challenging. – Keith Randall Jan 29 '11 at 4:10
• @SimpleCoder: I would assume monospace – JPvdMerwe Jan 29 '11 at 16:16

Here's my code, 494 characters in python:

import sys,re
Z=lambda c,s:re.findall(r'(\w)%s+(\d*)[^\w]*(\w)'%c,''.join(x*2for x in s))
T=lambda n:''.join(x for a in map(None,*n)for x in a if x)
E=Z('-',''.join(m))+Z('\\|',T(m))+Z('/',T(' '*m.index(s)+s for s in m))+Z('\\\\',T(' '*m[::-1].index(s)+s for s in m))
E+=[x[::-1]for x in E]
S={}
for x in E:S[x]=1e9
S['S']=0
P={}
for i in E:
for x,w,y in E:
w=int('1'+w)%10
if S[y]>S[x]+w:S[y]=S[x]+w;P[y]=x
i=p='T'
while i!='S':i=P[i];p=i+p
print'%d:'%S['T']+p