Untitled

from queue import PriorityQueue

import sys

graph = [
    [(1, 99), (2, 50)],
    [(4, 50), (3, 50), (2, 50)],
    [(3, 99)],
    [(4, 75)],
    [(5, 10)],
    []
]

vertex_distance = []
parent_vertexes = []


def dejkstra(graph: list, start_vertex: int):
    init_graph_vars(graph, start_vertex)

    available_vertexes_queue = PriorityQueue()
    available_vertexes_queue.put((0, start_vertex))

    while not available_vertexes_queue.empty():
        vertex_to_check = available_vertexes_queue.get()[1]
        for child_vertex_tuple in graph[vertex_to_check]:
            child_vertex = child_vertex_tuple[0]
            distance_to_child_vertex = vertex_distance[vertex_to_check] + child_vertex_tuple[1]
            if relax_edge(child_vertex, vertex_to_check, distance_to_child_vertex):
                available_vertexes_queue.put((distance_to_child_vertex, child_vertex))
    return vertex_distance


def relax_edge(child_vertex, parent_vertex, distance):
    if vertex_distance[child_vertex] > distance:
        parent_vertexes[child_vertex] = parent_vertex
        vertex_distance[child_vertex] = distance
        return True
    return False


def init_graph_vars(graph: list, start_vertex: int):
    global vertex_distance
    global parent_vertexes
    for vertex in graph:
        vertex_distance.append(sys.maxsize)
        parent_vertexes.append(None)
    vertex_distance[start_vertex] = 0

print(dejkstra(graph, 0))