Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #coding: utf-8
- class Graph:
- def loadfromfile(self, name):
- '''
- Метод, загружающий граф из файла.
- '''
- f = open(name, 'r')
- l = [line.strip() for line in f]
- self.n = int(l[0])
- self.names = {}
- self.invert_names = {}
- for x in l[1].split(', '):
- y = x.split(':')
- self.names[y[1]] = int(y[0]) - 1
- self.invert_names[int(y[0]) - 1] = y[1]
- self.g = [0] * self.n
- for i in range(self.n):
- self.g[i] = list(map(int, l[i + 2].split(' ')))
- def dijkstra_shortest_path(self, u):
- '''
- Метод, реализующий алгоритм Дейкстры.
- u - стартовая вершина.
- Алгоритм возвращает список пометок для всех вершин.
- '''
- d = [float('inf')] * self.n
- p = [0] * self.n
- u = self.names[u]
- d[u] = 0
- u = [False] * self.n
- for i in range(self.n):
- v = -1
- for j in range(self.n):
- if not u[j] and (v == -1 or d[j] < d[v]):
- v = j
- if d[v] == float('inf'):
- break
- u[v] = True
- for j in range(self.n):
- if self.g[v][j] > 0 and d[v] + self.g[v][j] < d[j]:
- d[j] = d[v] + self.g[v][j]
- p[j] = v
- self.d = d.copy()
- return p
- def dijkstra_get_path(self, u, v, l):
- '''
- Метод, печатающий список вершин, входящих в кратчайший путь от вершины u к вершине v.
- l - список пометок всех вершин.
- После списка вершин выводится длина кратчайшего пути.
- '''
- p = l.copy()
- path = []
- s = self.names[u]
- t = self.names[v]
- v = t
- while v != s:
- path.append(v)
- v = l[v]
- path.append(s)
- path.reverse()
- path = list(map(lambda x: self.invert_names[x], path))
- print('->'.join(path), '(' + str(self.d[t]) + ')')
- F = Graph()
- F.loadfromfile('1.txt')
- l = F.dijkstra_shortest_path('Pupkino')
- F.dijkstra_get_path('Pupkino', 'Kozulkino', l)
- G = Graph()
- G.loadfromfile('2.txt')
- l = G.dijkstra_shortest_path('x1')
- G.dijkstra_get_path('x1', 'x2', l)
- H = Graph()
- H.loadfromfile('3.txt')
- l = H.dijkstra_shortest_path('My')
- H.dijkstra_get_path('My', 'Highway', l)
Add Comment
Please, Sign In to add comment