Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
135 lines (109 sloc) 5.94 KB
# -*- coding:UTF-8 -*-
__author__ = 'Булыгина Настя bulygina07@yandex.ru, \
Булыгин В.В. bulygin69@yandex.ru'
'''
#Тренировка ЕГЭ по информатике
#Каталог заданий. Поиск оптимального маршрута по таблице
#https://inf-ege.sdamgia.ru/test?theme=213
G = {
'a': {'b':4},
'b': {'a':4, 'c':6, 'd':3, 'e':6},
'c': {'b':6, 'e':4},
'd': {'b':3, 'e':2},
'e': {'b':6, 'c':4, 'd':2, 'f':5 },
'f': {'e':5}
}
'''
#Пример из вики
#https://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
G = {
1: {2:7, 3:9, 6:14},
2: {1:7, 3:10, 4:15},
3: {4:11, 6:2, 1:9, 2:10},
6: {1:14, 5:9, 3:2},
5: {6:9, 4:6},
4: {5:6, 3:11, 2:15}
}
print('\n Граф G')
for i in G:
print(i, ':', G[i])
N = len(G) #количество элементов в словаре (G)
t = [] #список посещённых вершин
p = {} #словарь {открытая вершина : её метка}
b = {} #словарь для отслеживания короткого пути
v = None #текущая вершина
e = None #конечная вершина
def dijkstra(v, p, t, b, e):
print('\n Обходим всех соседей текущей вершины')
for x in G[v]: #для каждого соседа (х) текущей вершины (v)
xm = p[v] + G[v][x] #новая метка соседа (xm) =
#метка текущей вершины (p[v]) +
#значение ребра vx (G[v][x])
if not x in p: #если соседа (x) нет в словаре (p)
p[x] = xm #записываем новую метку (xm) в словарь с ключем (x)
b[x] = v #как только метка пересчитывается, запоминаем
#(следующая вершина: предыдущая вершина) в словаре (b)
elif not x in t: #иначе если (x) не в (t)
if p[x] > xm: #если старая метка соседа больше новой метки
p[x] = xm #новую метку записываем на место старой
b[x] = v #как только метка пересчитывается, запоминаем
#(следующая вершина: предыдущая вершина) в словаре (b)
print('текущей вершины v =', v, ' сосед x =', x, 'c меткой xm =', xm)
print('p =', p)
print('\n Добавляем текущую вершину в список посещенных')
t.append(v)
print('t =', t)
if N <= len(t): # Условие выхода из функции
print('\nВсё!\nВершины и их метки =', p)
print('Словарь для отслеживания пути =', b)
s = [] #кратчайший путь
s.insert(0, e) #вставляем (е) в список (s) по индексу (0)
while True:
if b[e] == -1: #значение ключа (-1) имеет начальная вершина
#вот её и ищем в словаре (b)
print('Кратчайший путь от начальной до конечной вершины =', s)
break #выходим из цикла
e = b[e] #теперь последней вершиной будет предыдущая
s.insert(0, e) #вставляем (е) в список (s) по индексу (0)
return s
print('\n Находим вершину с минимальной меткой за исключением тех, что уже в t')
for d in p: #вершина (d) с минимальной меткой из словаря (p)
if d not in t:
dm = p[d] #метка вершины (d)
break #пусть это будет первая вершина из словаря (p)
for y in p: #для каждой вершины (y) из словаря (p)
if p[y] < dm and not y in t: #если метка вершины (y) <
#метки вершины (d) & (y) нет в (t)
dm = p[y] #метку вершины (y) записываем в (dm)
d = y #вершину (y) записываем в (d)
print('Вершина y =', y, 'с меткой dm =', dm)
print('Вершина d =', d, 'имеет минимальную метку dm =', dm, \
'\nтеперь текущей вершиной v будет вершина d')
v = d #теперь текущей вершиной v будет вершина d
print('\n Рекурсивно вызываем функцию Дейкстры с параметрами v, p, t, b, e')
dijkstra(v, p, t, b, e)
##########
'''
# 2-й способ изменения глобальной переменной:
# объявляем необходимые переменные как global
def start_v(start, end):
global v, p, b, e
v = start
e = end
p[v] = 0
b[v] = -1
print('\n Начальная текущая вершина v =', v)
start_v(1, 5)
'''
# 1-й способ изменения глобальной переменой:
# используем возвращаемые значения
def start_v(start, end):
v = start
e = end
p[v] = 0
b[v] = -1
print('\n Начальная текущая вершина v =', v)
return v, p, b, e
v, p, b, e = start_v(1, 5) # иницилизация начальной и конечной вершин
dijkstra(v, p, t, b, e) # вызываем функцию Дейкстры
input()