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
|/     \|

    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:


Shortest correct program wins.

  • 1
    \$\begingroup\$ 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.) \$\endgroup\$
    – Thomas O
    Jan 28, 2011 at 20:21
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Jan 28, 2011 at 20:26
  • 3
    \$\begingroup\$ The input format is really far too complicated and imho doesn't really add that much to the problem. \$\endgroup\$
    – JPvdMerwe
    Jan 28, 2011 at 23:32
  • 1
    \$\begingroup\$ Just thought folks here would like to try something a bit more challenging. \$\endgroup\$ Jan 29, 2011 at 4:10
  • 2
    \$\begingroup\$ @SimpleCoder: I would assume monospace \$\endgroup\$
    – JPvdMerwe
    Jan 29, 2011 at 16:16

1 Answer 1


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]
for x in E:S[x[0]]=1e9
for i in E:
 for x,w,y in E:
  if S[y]>S[x]+w:S[y]=S[x]+w;P[y]=x
while i!='S':i=P[i];p=i+p

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.