Условие:
Найти и вывести кратчайший путь в неориентированном графе, все
рёбра которого имеют единичный вес, между двумя заданными вершинами. Начальную и конечную вершины ввести с клавиатуры. Граф задан
в текстовом файле матрицей смежности.
Решение:
Ниже приведён один из возможных вариантов решения задачи на языке Python. Алгоритм использует обход в ширину (BFS) для нахождения кратчайшего пути в неориентированном графе, где все ребра имеют единичный вес. Ниже приведён пошаговый разбор решения: ───────────────────────────── Шаг 1. Чтение графа из файла ───────────────────────────── • Граф задан матрицей смежности, поэтому первым делом считываем содержимое файла (например, graph.txt). • Каждая строка файла соответствует строке матрицы смежности. • Преобразуем считанные строки в двумерный список (матрицу). ────────────────────────────...
from collections import deque def readname): Считывает граф из файла, где граф задан матрицей смежности. Возвращает матрицу в виде списка списков. graph = [] with open(fileame, r, encoding=utf-8) as f: for line in f: # Удаляем лишние пробелы и разбиваем строку на числа # Предполагается, что числа разделены пробелами row = list(map(int, line.strip().split())) if row: graph.append(row) return graph def bfspath(graph, start, end): Поиск кратчайшего пути в невзвешенном графе с помощью BFS. graph - матрица смежности; start - начальная вершина; end - конечная вершина. Возвращает список вершин кратчайшего пути или None, если путь не существует. n = len(graph) # Список для отметки посещённых вершин visited = [False] * n # Словарь для восстановления пути: для каждой вершины - её предок prev = [None] * n # Инициализируем очередь и запускаем BFS с начальной вершины queue = deque() queue.append(start) visited[start] = True while queue: current = queue.popleft() # Если достигли целевой вершины, готовимся восстановить путь if current == end: break # Проходим по всем вершинам, смежным с current for neighbor in range(n): # Если есть ребро: проверяем, не посещена ли уже соседняя вершина if graph[current][neighbor] != 0 and not visited[neighbor]: queue.append(neighbor) visited[neighbor] = True prev[neighbor] = current # Если конечная вершина не достигнута, возвращаем None if not visited[end]: return None # Восстанавливаем путь, двигаясь от end к start path = [] at = end while at is not None: path.append(at) at = prev[at] path.reverse() # разворачиваем список, чтобы путь шел от start к end return path def main(): # Чтение графа из файла graph.txt graph = readraph(graph.txt) # Ввод начальной и конечной вершин с клавиатуры. # Убедитесь, что введенные номера соответствуют нумерации в матрице (например, от 0) try: start = int(input(Введите номер начальной вершины (начинается с 0): )) end = int(input(Введите номер конечной вершины (начинается с 0): )) except ValueError: print(Ошибка: введите корректное числовое значение.) return # Проверка корректности введённых номеров вершин n = len(graph) if start 0 or start = n or end 0 or end = n: print(Ошибка: введён некорректный номер вершины.) return # Нахождение кратчайшего пути BFS path = bfspath(graph, start, end) if path is None: print(Путь между вершинами не найден.) else: print(Кратчайший путь:, - .join(map(str, path))) if == : main() ───────────────────────────── Пошаговое объяснение работы кода: ───────────────────────────── 1. Функция readraph() открывает файл graph.txt и считывает по строкам матрицу смежности, преобразуя каждую строку в список целых чисел. 2. В функции main() пользователю предлагается ввести номера начальной и конечной вершин. При этом предполагается, что нумерация начинается с 0. 3. Функция bfspath() реализует алгоритм обхода в ширину (BFS): – Инициализируется очередь и массив visited для отслеживания уже посещённых вершин. – Для каждой вершины, смежной с текущей, если она не посещена, происходит её добавление в очередь. – Словарь prev (в данном случае список, где prev[i] – предшественник вершины i) заполняется для последующего восстановления пути. – Если целевая вершина достигается, происходит выход из цикла. 4. Если целевая вершина была посещена, восстанавливается путь от конца к началу, используя список prev, далее список переворачивается. 5. Полученный кратчайший путь выводится в виде последовательности номеров вершин, разделённых стрелками. ───────────────────────────── Таким образом, представленный код решает задачу нахождения кратчайшего пути в неориентированном графе с ребрами единичного веса, заданном матрицей смежности в текстовом файле.