Shortest path in a graph

Question

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.

Answer 1

Here's my code, 494 characters in python:

import sys,re
m=sys.stdin.readlines()
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[0]]=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