# Untitled

unknown
plain_text
3 years ago
1.5 kB
8
Indexable
Never
```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))```