dijkstra_modification.py - master - anz/AAB_algorithms

dijkstra_modification.py
101 строка4 KB
anz
домашнее задание по графам
07 июн 2025, 21:23
07 июн 2025, 21:23f3d2473
from collections import defaultdict
class Graph:
    def __init__(self):
        self.vertices = set()
        #hashmap где ключи вершины, а значение list из туплей.например,'A':[(B,2), (C, 6)]
        self.edges = defaultdict(list)
    def add_vertex(self, vertex):
        self.vertices.add(vertex)
    def add_edge(self, source, destination, weight):
        self.vertices.add(source)
        self.vertices.add(destination)
        self.edges[source].append((destination, weight))
    def get_neighbours(self, vertex):
        return self.edges[vertex]
class PriorityQueue:
    def __init__(self):
        self.heap = []
    def parent(self, i):
        return (i - 1) // 2  #Возвращает индекс родительского узла для узла с индексом i
    def _left(self, i):
        return 2 * i + 1  #Возвращает индекс левого ребёнка узла с индексом i
    def _right(self, i):
        return 2 * i + 2  #Возвращает индекс правого ребёнка узла с индексом i
    def sift_up(self, i):
        while i > 0 and self.heap[self.parent(i)][0] > self.heap[i][0]:
            self.heap[self.parent(i)], self.heap[i] = self.heap[i], self.heap[self.parent(i)]
            i = self.parent(i)
    def sift_down(self, i):
        min_index = i
        left = self._left(i)
        right = self._right(i)
        size = len(self.heap)

        if left < size and self.heap[left][0] < self.heap[min_index][0]:
            min_index = left
        if right < size and self.heap[right][0] < self.heap[min_index][0]:
            min_index = right
        if i != min_index:
            self.heap[i], self.heap[min_index] = self.heap[min_index], self.heap[i]
            self.sift_down(min_index)
    def push(self, item):
        #Добавляет элемент в кучу и восстанавливает её структуру
        self.heap.append(item)
        self.sift_up(len(self.heap) - 1)
    def pop(self):
        #Удаляет и возвращает минимальный элемент из кучи
        if not self.heap:
            raise IndexError('pop from empty priority queue')
        result = self.heap[0]
        last = self.heap.pop()
        if self.heap:
            self.heap[0] = last
            self.sift_down(0)
        return result
    def is_empty(self):
        return len(self.heap) == 0



def dijkstra_2(graph, source):
    distance = {vertex: float('infinity') for vertex in graph.vertices}
    distance[source] = 0
    predecessor = {vertex: None for vertex in graph.vertices}
    processed = set()

    pq = PriorityQueue()
    pq.push((0, source))

    while not pq.is_empty():
        current_distance, current = pq.pop()  #Извлекаем вершину с минимальным расстоянием
        if current in processed or distance[current] < current_distance:
            continue  #Если вершина уже обработана или найдено лучшее расстояние
        processed.add(current)

        for neighbour, weight in graph.get_neighbours(current):
            if neighbour in processed:
                continue
            new_distance = current_distance + weight
            if new_distance < distance[neighbour]:
                distance[neighbour] = new_distance
                predecessor[neighbour] = current
                pq.push((new_distance, neighbour))

    return distance, predecessor

graph = Graph()
graph.add_edge('St', 'A', 5)
graph.add_edge('St', 'D', 13)
graph.add_edge('St', 'E', 3)
graph.add_edge('A', 'D', 6)
graph.add_edge('A', 'B', 1000)
graph.add_edge('B', 'C', 5)
graph.add_edge('D', 'B', 15)
graph.add_edge('D', 'C', 3)
graph.add_edge('D', 'E', 100)

distances, predecessors = dijkstra_2(graph, 'St')

print("Кратчайшие расстояния от St:")
for vertex in distances:
    print(f"{vertex}: {distances[vertex]}")