Быстрый алгоритм дейкстры. Правильна ли реализация и можно ли ускорить?

Вот условия задачи:

Вам дано описание дорожной сети страны. Ваша задача – найти длину кратчайшего пути между городами А и B.

Формат ввода Сеть дорог задана во входном файле следующим образом: первая строка содержит числа N и K (1 ≤ N ≤ 100000, 0 ≤ K ≤ 300000), где K – количество дорог. Каждая из следующих K строк содержит описание дороги с двусторонним движением – три целых числа ai, bi и li (1 ≤ ai, bi ≤ N, 1 ≤ li ≤ 106). Это означает, что имеется дорога длины li, которая ведет из города ai в город bi. В последней строке находятся два числа А и В – номера городов, между которыми надо посчитать кратчайшее расстояние (1 ≤ A, B ≤ N)

Формат вывода Выведите одно число – расстояние между нужными городами. Если по дорогам от города А до города В доехать невозможно, выведите –1.

Вот моя реализация:

class Heap:
    def __init__(self):
        self.mass = []

    def push(self, ind, value):
        heap = self.mass
        heap.append((ind, value))
        i = len(heap) - 1
        while heap[i][1] < heap[(i + 1 // 2)][1]:
            heap[i], heap[(i + 1) // 2] = heap[(i + 1) // 2], heap[i]
            i = (i + 1) // 2

    def pop(self):
        heap = self.mass
        last = heap[len(heap) - 1]
        first = heap[0]
        heap[0] = last
        i = 0
        n = len(heap)
        if n == 1:
            return first[0]
        while 2 * i + 2 < n:
            left = 2 * i + 1
            right = 2 * i + 2
            if heap[left][1] < heap[right][1]:
                z = left
            else:
                z = right
            if heap[z][1] < heap[i][1]:
                heap[z], heap[i] = heap[z], heap[i]
                i = z
            else:
                heap.pop()
                return first[0]
        heap.pop()
        return first[0]


# Простое создание графа в виде списка смежности
def create_graph():
    n, k = map(int, input().split())
    graph = dict()
    for i in range(n):
        graph[i] = []
    for i in range(k):
        a, b, l = map(int, input().split())
        graph[a - 1].append((b - 1, l))
        graph[b - 1].append((a - 1, l))
    start, end = map(int, input().split())
    return graph, n, start, end


def find_min_dist(dist, is_visited):
    infinity = 10000000000
    result = None
    for i in range(len(dist)):
        if is_visited[i] == 0 and infinity > dist[i]:
            infinity = dist[i]
            result = i
    return result


def algo_d(graph, n, start, end):
    heap = Heap()
    # создаю два заранее заполненных массива, в dist_mass храню расстояние от тееущей вершины до начальной
    is_visited = [-1] * n 
    dist_mass = [1000000000] * n
    dist_mass[start] = 0
    is_visited[start] = 1 # у is_visited 3 состояния, 0 - не посещена, но известно расстояние до нее, 1 - посещена, -1 - не звестно расстояние до нее 
    # 3 состояния связано с прошлой реализацией алгоритма - искал минимальное расстояние через функцию find_min_dist, нынешняя реализация на heap
    for vertex, dist in graph[start]: # распаковываем ребра начальной вершины
        if dist_mass[vertex] > dist: 
            dist_mass[vertex] = dist
            is_visited[vertex] = 0
            heap.push(vertex, dist) # добавляем номер вершины и расстояние от начальной до нее в кучу

    while 0 in is_visited: # если есть 0 в массиве, то распаковка не закончена, если остались только 1 - то распаковка закончена, если же осталась -1, то до этой вершины добраться нельзя
        node = heap.pop() # извлекаем номер вершины, до которой топать меньше всего
        is_visited[node] = 1
        for vertex, dist in graph[node]: # распаковываем эту вершину
            if dist_mass[vertex] > dist + dist_mass[node]:
                dist_mass[vertex] = dist_mass[node] + dist
                is_visited[vertex] = 0
                heap.push(vertex, dist)

    if is_visited[end] == -1:
        return -1
    else:
        return dist_mass[end]


graph, n, start, end = create_graph()
print(algo_d(graph, n, start - 1, end - 1))

Мои комментарии:

Сразу скажу, с каким конкретно недопонимаем я столкнулся.

Мы ищем выбираем вершину, к которой идти кратчайшим путем, но мы все равно посещаем каждую вершину. Пример матрицы смежности (-1) - пути нет:

1 2 3 4
0 1 2 1000
1 0 2 -1
-1 2 0 100
1000 -1 100 0

Пусть нам нужно попасть из первой вершины в третью, смотрим на соседей первой - это 2 и 4, кидаем их в кучу, кратчайший путь равен 1, из кучи выйдет вершина с номером 2 - расспаковываем, получаем, что до 3 вершины добираем за путь = 3 Опять выбираем минимальное, то есть путь = 3, из кучи выходит вершина 3 - ее сосед 4, расстояние до него 103 Выбираем минимальное из 1000 и 103, то есть 103 И того - мы посетили все вершины, то есть сложность O(V), где V - количество вершин, но при этом мы извлекали и добавляли каждую вершину (O(2logN) из кучи(для каждой вершины), для поиска минимального расстояния, то есть итоговое - O(V*logV) Допускал, что количество ребер < V, поэтому в вычислениях не учитывал

Так вот, теперь подходим к главному вопросу, почему асимптотика алгоритма без поиска вершины с кратчайшим путем хуже? Допустим мы не выбираем кратчайший путь до вершинны, а все непощенные кидаем в массив, и достаем(любую с последующим удалением), когда понадобится. Таким образом получение очередной вершины будет занимать O(1), а не O(LogV)

Опробывал код с переделанной кучей на массив: Так же валится на 6 - ом тесте.

class Heap:
    def __init__(self):
        self.mass = []

    def push(self, ind, value):
        heap = self.mass
        heap.append(ind)

    def pop(self):
        heap = self.mass
        red = heap[-1]
        heap.pop()
        return red

И итог:

Эта задача с контеста яндекса по тренировкам 4.0 Мне кажется, что где-то в алгоритме дейкстры я не допонял задумку, именно поэтому у меня валится 6-ой тест по времени, хотя асимптотика вроде не плохая.

Если кто-то видит ошибку в моих рассуждениях или ошибку в коде, которая сильно портит асимптотику - пожалуйста укажите на это.