Как найти наибольший путь в графе

class Vertex:
    def __init__(self, id, name):
        self.id = id
        self.name = name
        self.minDistance = float('inf')
        self.previousVertex = None
        self.edges = []
 
    def __str__(self):
        return "{"+str(self.id)+"}"
 
 
class Edge:
    def __init__(self, source, target, weight):
        self.source = source
        self.target = target
        self.weight = weight
 
# Находим кратчайшее расстояние с помощью Дейкстры
 
 
class Dijkstra:
    def __init__(self):
        self.vertexes = []
        self.start = None
        pass
 
    def createGraph(self, vertexes, edgesToVertexes):
        self.vertexes = vertexes
        for edge in edgesToVertexes:
            for vertex in vertexes:
                if vertex.id == edge.source:
                    vertex.edges.append(edge)
 
    def computePath(self, sourceId):
        self.start = sourceId
        visit = []
        visited = []
        for item in self.vertexes:
            if item.id == sourceId:
                item.minDistance = 0
                item.previousVertex = sourceId
            visit.append(item.id)
 
        while len(visited) != len(visit):
            start = self.getMin(visited)
 
            for edge in start.edges:
                end = self.getVertex(edge.target)
                way = start.minDistance + edge.weight
                if end.minDistance >= way:
                    end.previousVertex = start.id
                    end.minDistance = way
            visited.append(start.id)
 
    def getShortestPathTo(self, targetId):
        way = []
        tmp = self.getVertex(targetId)
        way.insert(0, tmp)
        while tmp.previousVertex != tmp.id:
            tmp = self.getVertex(tmp.previousVertex)
            if tmp is None:
                break
            way.insert(0, tmp)
        return way
 
    def getMin(self, array):
        min = Vertex('a', 'tmp')
        min.minDistance = float('inf')
        for item in self.vertexes:
            if (item.minDistance <= min.minDistance) and (item.id not in array):
                min = item
        return min
 
    def getVertex(self, id):
        vertex = None
        for item in self.vertexes:
            if item.id == id:
                vertex = item
                break
        return vertex
 
    def getVertexes(self):
        return self.vertexes
 
 
with open('input_graph1.txt') as f:
    matrix =[list(map(int, row.split())) for row in f.readlines()]
 
n = len(matrix)
 
try:
    a = int(input("Откуда ? : "))
    b = int(input("Куда ? : "))
 
    if (a > 0) and (b > 0) and (a <= 15) and (b <= 15):
        a = a - 1
        b = b - 1
 
        vertexes = []
        edges = []
        for i in range(len(matrix)):
            v = Vertex(i, str(i + 1))
            for k in range(len(matrix[i])):
                if matrix[i][k] == 0:
                    continue
                e = Edge(i, k, matrix[i][k])
                edges.append(e)
            vertexes.append(v)
 
        dijkstra = Dijkstra()
        dijkstra.createGraph(vertexes, edges)
 
        vertexToCompute = vertexes[a]
        dijkstra.computePath(a)
        path = dijkstra.getShortestPathTo(b)
        for vertex in path:
            print("Путь -> " + str(vertex.name))
        print("Минимальное расстояние: " + str(vertexes[b].minDistance))
    else:
        print("Введенное число(а) не в интервале 1..15")
except ValueError:
    print("Введенное значения не число")