/
evabaraniuk
/
homework
Обзор
Документация
Войти
/
evabaraniuk
/
homework
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
CI/CD
Аналитика
Безопасность
master
task2
56 строк
2 KB
evabaraniuk
update task2
07 июн 2025, 13:25
07 июн 2025, 13:25
de95ca0
Код
Авторство
О чём код?
from dll import DoublyLinkedList def bfs_shortest_paths(graph, start): visited = set() queue = DoublyLinkedList.build([(start, [start], 0)]) shortest_paths = {} distances = {} while queue.len() > 0: node, path, distance = queue.delete_last() if node not in visited: visited.add(node) shortest_paths[node] = path distances[node] = distance for neighbor in graph.get(node, []): if neighbor not in visited: new_path = path + [neighbor] new_distance = distance + 1 queue.insert_first((neighbor, new_path, new_distance)) return shortest_paths, distances def print_shortest_paths(shortest_paths, distances, start): print(f"Кратчайшие пути от вершины {start}:") print("-" * 40) for vertex in sorted(shortest_paths.keys()): if vertex != start: path = " -> ".join(shortest_paths[vertex]) distance = distances[vertex] print(f"До {vertex}: {path} (расстояние: {distance})") else: print(f"До {vertex}: {vertex} (расстояние: 0)") graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E', 'G'], 'G': ['F'] } if __name__ == "__main__": start_vertex = 'A' paths, distances = bfs_shortest_paths(graph, start_vertex) print_shortest_paths(paths, distances, start_vertex) print("\nДетальная информация:") print("Кратчайшие пути:", paths) print("Расстояния:", distances)