Алгоритм Дейкстры

#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):
        '''
    Метод, реализующий алгоритм Дейкстры.
    Алгоритм возвращает список пометок для всех вершин.
    '''
        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):
        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]) + ')')