dij

import math
from dataclasses import dataclass
from typing import Generic, Optional
from typing import List, Tuple
import heapq
from graph import Graph, T

def dijkstra(graph: Graph[T], start: T, end: T) -> Tuple[List[T], int]:
    heap: List[Tuple[int, T]] = [(0, start)] #очередь приоритетов
    distances: List[int] = [float('inf')] * graph.length #просто расстояния. изначально бесконечность
    predecessors: List[Optional[int]] = [None] * graph.length #сохраняем соседей (предшественников) каждой вершины с меньшим путем
    distances[graph.vertex_names[start]] = 0 #сохарняем минимальные расстояния до каждой вершинв

    while heap:
        current_distance, current_vertex = heapq.heappop(heap) #убираем наименьшие значения расстояния и вершины из очереди

        if current_vertex == end: #когда дошли до конца - восстанавливаем путь с конца к началу
            path = []
            current = graph.vertex_names[end] #встаем на позицию финиша
            while predecessors[current] is not None:
                path.append(graph.get_vertex_by_index(current)) #просто вытаскиваем названия вершин по индексам
                current = predecessors[current] #дивагемся дальше (на предшественника текущего)
            path.append(start) #добавлям старт
            return path[::-1], current_distance #путь пишем в обратном порядке, возвращаем расстояние

        for neighbor_index, weight in enumerate(graph.matrix[graph.vertex_names[current_vertex]]): #Перебрать соседей текущей вершины.
            if weight != 0:
                distance = current_distance + weight # смотрим новое расстояние
                if distance < distances[neighbor_index]: # Если найден более короткий путь к соседу
                    distances[neighbor_index] = distance
                    predecessors[neighbor_index] = graph.vertex_names[current_vertex]
                    heapq.heappush(heap, (distance, graph.get_vertex_by_index(neighbor_index)))
                    # обновляем расстояние, предшественника и помещаем все это в очередь приоритетов.
    return [], 0