task3 - master - evabaraniuk/homework

task3
84 строки3 KB
evabaraniuk
update task3
07 июн 2025, 13:25
07 июн 2025, 13:250e1632b
from priority_queue import DijkstraPriorityQueue
from graph import Graph

def dijkstra_with_custom_heap(graph, source):
    # Инициализация расстояний
    distances = {vertex: float('infinity') for vertex in graph.vertices}
    distances[source] = 0
    
    # Инициализация предшественников для восстановления путей
    predecessors = {vertex: None for vertex in graph.vertices}
    
    # Создаем очередь с приоритетом
    pq = DijkstraPriorityQueue()
    
    # Добавляем все вершины в очередь
    for vertex in graph.vertices:
        pq.push_vertex(distances[vertex], vertex)
    
    # Множество обработанных вершин
    processed = set()
    
    while not pq.is_empty():
        current_distance, current_vertex = pq.pop_vertex()
        
        # Пропускаем, если вершина уже обработана или расстояние устарело
        if current_vertex in processed or current_distance > distances[current_vertex]:
            continue
        
        processed.add(current_vertex)
        
        # Обновляем расстояния до соседей
        for neighbor, weight in graph.get_neighbours(current_vertex):
            if neighbor not in processed:
                new_distance = distances[current_vertex] + weight
                
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance
                    predecessors[neighbor] = current_vertex
                    # Добавляем обновленное расстояние в очередь
                    pq.push_vertex(new_distance, neighbor)
    
    return distances, predecessors

def reconstruct_path(predecessors, source, target):
    if predecessors[target] is None and target != source:
        return None  # Путь не существует
    
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = predecessors[current]
    
    path.reverse()
    return path

def print_dijkstra_results(distances, predecessors, source):
    print(f"Кратчайшие расстояния от вершины {source}:")
    print("-" * 50)
    
    for vertex in sorted(distances.keys()):
        distance = distances[vertex]
        if distance == float('infinity'):
            print(f"До {vertex}: недостижима")
        else:
            path = reconstruct_path(predecessors, source, vertex)
            path_str = " -> ".join(path) if path else "недостижима"
            print(f"До {vertex}: расстояние {distance}, путь: {path_str}")

if __name__ == "__main__":
    graph = Graph()

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

    distances, predecessors = dijkstra_with_custom_heap(graph, 'St')
    print(distances)