Shortest path in a graph

12

1

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.

Keith Randall

Posted 2011-01-28T17:17:01.923

Reputation: 19 865

Puzzles, where you must write the shortest code outputing the best output have a problem: they can be solved by generation random outputs until it suits the task. So such puzzles better should have not the shortest solution but the fastest. But shortest path in graph is trivial, so no sense of fastest, then you may specify, that you want to get the shortest solution with complexity of O(<???) or maybe some another way to determine goal effectiveness. – Nakilon – 2011-01-28T17:37:06.110

I'm looking for the shortest program. Go ahead and randomly generate solutions and test them if you think that will get you a shorter program. Keep in mind your program must always be correct. – Keith Randall – 2011-01-28T18:01:47.517

1Does 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 – 2011-01-28T20:21:51.210

Algorithm wise, an MST or Dijkstra comes to mind. – Thomas O – 2011-01-28T20:23:09.413

1Yes, 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 – 2011-01-28T20:26:59.857

3The input format is really far too complicated and imho doesn't really add that much to the problem. – JPvdMerwe – 2011-01-28T23:32:56.613

1Just thought folks here would like to try something a bit more challenging. – Keith Randall – 2011-01-29T04:10:53.017

Differences in character widths could possibly ruin the alignment, especially across different fonts. For this reason, I agree that the input format is too complicated. – Chris Laplante – 2011-01-29T14:27:58.427

2@SimpleCoder: I would assume monospace – JPvdMerwe – 2011-01-29T16:16:16.080

Answers

5

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

Keith Randall

Posted 2011-01-28T17:17:01.923

Reputation: 19 865

Asked: 2011-01-28T17:17:01.923

Viewed: 930 times

Active: 2014-12-23T16:53:11.960