Решение задачи #13. Python Яндекс CodeRun, Путь в графе

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Название задачи:
Статус решения: "Решено".

Условие задачи:
В неориентированном графе требуется найти минимальный путь между двумя вершинами.

Формат ввода:
Первым на вход поступает число N – количество вершин в графе (1 ≤≤ N ≤≤ 100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Далее задаются номера двух вершин – начальной и конечной.

Формат вывода:
Выведите сначала L – длину кратчайшего пути (количество ребер, которые нужно пройти), а потом сам путь. Если путь имеет длину 0, то его выводить не нужно, достаточно вывести длину. Необходимо вывести путь (номера всех вершин в правильном порядке). Если пути нет, нужно вывести -1.

Решение:

Python
import sys
from collections import deque

def main():
    # Чтение входных данных
    N = int(input())  # Количество вершин в графе
    graph = [list(map(int, input().split())) for _ in range(N)]  # Матрица смежности графа
    start, end = map(int, input().split())  # Начальная и конечная вершины (нумерация с 1)

    # Если начальная и конечная вершины совпадают
    if start == end:
        print(0)  # Путь имеет длину 0
        return

    # Преобразуем нумерацию вершин с 1..N на 0..N-1 для удобства работы
    start -= 1
    end -= 1

    # Обход в ширину (BFS) для поиска кратчайшего пути
    queue = deque([start])  # Очередь для BFS
    visited = [-1] * N  # Массив расстояний до вершин (-1 означает "не посещена")
    parent = [-1] * N  # Массив для восстановления пути
    visited[start] = 0  # Расстояние до начальной вершины равно 0

    while queue:
        current = queue.popleft()  # Извлекаем текущую вершину из очереди
        for neighbor in range(N):  # Перебираем всех соседей текущей вершины
            if graph[current][neighbor] == 1 and visited[neighbor] == -1:  # Если есть ребро и сосед не посещён
                visited[neighbor] = visited[current] + 1  # Обновляем расстояние
                parent[neighbor] = current  # Запоминаем предка
                queue.append(neighbor)  # Добавляем соседа в очередь

    # Если конечная вершина недостижима
    if visited[end] == -1:
        print(-1)
        return

    # Восстановление пути
    path = []
    current = end
    while current != -1:  # Идём от конечной вершины к начальной через массив parent
        path.append(current + 1)  # Преобразуем обратно к нумерации с 1
        current = parent[current]
    path.reverse()  # Переворачиваем путь, чтобы он шёл от начальной к конечной вершине

    # Вывод результата
    print(visited[end])  # Длина пути
    if visited[end] > 0:  # Если длина пути больше 0, выводим сам путь
        print(*path)


if __name__ == '__main__':
    main()
	

Объяснение кода

1. Чтение входных данных
Мы считываем количество вершин N и матрицу смежности графа.
Матрица смежности — это двумерный массив размером N×N, где элемент graph[i][j] равен 1, если между вершинами i и j есть ребро, и 0, если нет.
Также считываем номера начальной (start) и конечной (end) вершин.

2. Обработка случая, когда начальная и конечная вершины совпадают
Если start == end, то путь имеет длину 0, и его не нужно выводить. Просто выводим 0.

3. Преобразование нумерации вершин
Для удобства работы преобразуем нумерацию вершин с 1..N на 0..N-1.

4. Поиск кратчайшего пути с помощью BFS
Мы используем алгоритм обхода в ширину (BFS), который гарантирует нахождение кратчайшего пути в невзвешенном графе.
Создаём очередь queue для хранения вершин, которые нужно обработать.
Создаём массив visited, где visited[i] хранит расстояние от начальной вершины до вершины i. Изначально все значения равны -1 (вершины не посещены).
Создаём массив parent, где parent[i] хранит предка вершины i для восстановления пути.

5. Обход графа
Пока очередь не пуста:
Извлекаем текущую вершину из очереди.
Перебираем всех её соседей. Если сосед ещё не посещён, обновляем его расстояние, запоминаем предка и добавляем его в очередь.

6. Проверка достижимости конечной вершины
Если visited[end] == -1, это означает, что конечная вершина недостижима. В этом случае выводим -1.

7. Восстановление пути
Если конечная вершина достижима, восстанавливаем путь, двигаясь от конечной вершины к начальной через массив parent.
Преобразуем нумерацию обратно к 1..N и переворачиваем путь, чтобы он шёл от начальной к конечной вершине.

8. Вывод результата
Выводим длину пути (visited[end]).
Если длина пути больше 0, выводим сам путь.

Пример работы программы:
Ввод:
5
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
1 5

Вывод:
2
1 2 3 4 5

Объяснение:
Граф содержит путь из вершины 1 в вершину 5 через вершины 2, 3 и 4.
Длина пути равна 4.

Пример без пути:
Ввод:
4
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
1 4

Вывод:
-1

Объяснение:
Вершина 1 и вершина 4 находятся в разных компонентах связности, поэтому путь между ними отсутствует.

Детали реализации:
Сложность алгоритма :
Временная сложность: O(N2), так как мы используем матрицу смежности.
Пространственная сложность: O(N2) для хранения матрицы смежности и O(N) для массивов visited и parent.

Ограничения:
Код работает корректно при N≤100, что соответствует ограничениям задачи.
Алгоритм укладывается в ограничения по времени и памяти.

Обработка граничных случаев:
Если начальная и конечная вершины совпадают, программа выведет 0.
Если пути нет, программа выведет -1.

Источник решения: hdhai.com