Ниже приведён один из возможных вариантов решения задачи на языке 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. Полученный кратчайший путь выводится в виде последовательности номеров вершин, разделённых стрелками.

───────────────────────────── Таким образом, представленный код решает задачу нахождения кратчайшего пути в неориентированном графе с ребрами единичного веса, заданном матрицей смежности в текстовом файле.