Кратчайший путь в графе

12

Напишите программу, чтобы взять график (из стандартного ввода или файла, на ваш выбор) и найти кратчайший путь в графике.

Графики указываются в следующем формате:

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

Все ребра ненаправлены и лежат вдоль одного из 8 основных направлений (то есть без изгибов). Ребра могут дополнительно содержать вес от 0 до 9. Вес не будет на последнем символе, который соединяет ребро с узлом (то есть ребра должны содержать не менее 3 символов, чтобы содержать вес). Невзвешенные ребра имеют вес по умолчанию 1.

Ваш код должен вычислить кратчайший путь между узлами Sи Tи напечатать длину и путь, как это:

5:SDEFT

Короче правильная программа выигрывает.

code-golf graph-theory path-finding Кит Рэндалл
источник
1
Нужно ли анализировать графическую диаграмму или вы можете использовать свой собственный формат? Один из примеров формата - ваш график может быть представлен как: AS0,SD0,SE5,DE3,FE0,FT0(вы можете опустить запятые, если каждая запись имеет длину 3 байта.)
Thomas O
1
Да, вы должны проанализировать график, как я указал. Это большая часть проблемы, на самом деле. Самая короткая часть пути просто гарантирует, что ваш анализ правильный.
Кит Рэндалл
3
Формат ввода на самом деле слишком сложен, и imho на самом деле не так уж много добавляет к проблеме.
JPvdMerwe
1
Просто подумал, что люди здесь хотели бы попробовать что-то более сложное.
Кит Рэндалл
2
@SimpleCoder: я бы предположил,
монопространство

Ответы:

5

Вот мой код, 494 символа в 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
Кит Рэндалл
источник