прикреплённый файл:2013-02-15.trip.py к странице LecturesVMSH/Python/2013-02-15

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Таблица N×N содержит стоимости прямого проезда из города i в город j (i<N, j<N, i≠j). Стоимость проезда не превышает S, если из города i в город j проезда нет, в таблице стоит S*N.
   5 
   6     Определить минимальную стоимость проезда из города A в город B с учётом возможных пересадок
   7     …вывести также любой маршрут из A в B с минимальной стоимостью проезда
   8     составить таблицу минимальной стоимости проезда из любого города в любой
   9 '''
  10 
  11 import sys, itertools, copy
  12 
  13 if len(sys.argv)>1:
  14     # Генератор
  15     from random import randrange, sample
  16     N=int(sys.argv[1])
  17     Proc=len(sys.argv)>2 and int(sys.argv[2]) or 30
  18     S=100
  19     L=sample([(i,j) for i in xrange(N) for j in xrange(N) if i!=j], N*N*Proc/100)
  20     M=[[(i,j) in L and randrange(1,S) or S*N*N for i in xrange(N)] for j in xrange(N)]
  21     print M
  22     sys.exit(0)
  23 
  24 def Floyd(Map):
  25     '''Метод Флойда'''
  26     Next=True
  27     while Next:
  28         Next=False
  29         for i in xrange(len(Map)):
  30             for j in xrange(len(Map)):
  31                 for k in xrange(len(Map)):
  32                     if i!=k and j!=k and Map[i][j]>Map[i][k]+Map[k][j]:
  33                         # Есть такой научный термин: релаксация связи
  34                         Next=True
  35                         Map[i][j]=Map[i][k]+Map[k][j]
  36     
  37 
  38 def Dijkstra(Map,s):
  39     '''Метод Дейкстры'''
  40     def get1(e): return e[1][1]
  41     # Пока из города s никуда не доехать
  42     Next=[[i,MAX] for i in xrange(len(Map))]
  43     # …кроме самого s, что бесплатно
  44     Next[s]=[s,0]
  45     Res=[]
  46     # Для каждого города
  47     while Next:
  48         # Выберем такой город s, к которому дешевле ехать
  49         i,(s,w)=min(enumerate(Next),key=get1)
  50         Res.append(Next.pop(i))
  51         # Для всех оставшихся городов
  52         for i,(town,way) in enumerate(Next):
  53             if Map[s][town]<MAX:
  54                 # Проверим, не дешевле ли доехать до них через s
  55                 if way>w+Map[s][town]:
  56                     Next[i]=[town,w+Map[s][town]]
  57     return zip(*sorted(Res))[1]
  58 
  59 def prinTab(Map,w=4):
  60     print "_"*len(Map)*w
  61     print "\n".join(" ".join(("{0:"+str(w-1)+"}").format(c==MAX and " # " or c) for c in l) for l in Map)
  62 
  63 Inp=input()
  64 MAX=max(itertools.chain(*Inp))
  65 prinTab(Inp)
  66 
  67 Map=copy.deepcopy(Inp)
  68 print "_"*len(Map)*4
  69 print " ".join("{0:3}".format(c) for c in Dijkstra(Map,0))
  70 Floyd(Map)
  71 prinTab(Map)