Решение задачи #12. Python Яндекс CodeRun, Длина кратчайшего пути

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Длина кратчайшего пути.
Сложность: Лёгкая.
Статус решения: "Решено".

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

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

Формат вывода:
Выведите длину кратчайшего пути — минимальное количество ребер, которые нужно пройти. Если пути нет, нужно вывести -1.

Решение:

Python

import sys
from collections import deque

def main():
    # Чтение входных данных
    n = int(sys.stdin.readline())
    graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    start, end = map(int, sys.stdin.readline().split())

    # Инициализация массива для отслеживания расстояний до каждой вершины
    distance = [-1] * n
    distance[start - 1] = 0  # Расстояние до начальной вершины равно 0

    # Инициализация очереди для обхода графа в ширину
    queue = deque()
    queue.append(start - 1)

    # Поиск кратчайшего пути в графе в ширину
    while queue:
        curr_vertex = queue.popleft()
        # Итерируемся по всем смежным вершинам
        for i in range(n):
            # Если граф связан с текущей вершиной и расстояние до смежной вершины не определено
            if graph[curr_vertex][i] == 1 and distance[i] == -1:
                # Обновляем расстояние до смежной вершины
                distance[i] = distance[curr_vertex] + 1
                # Добавляем смежную вершину в очередь
                queue.append(i)

    # Вывод результата
    print(distance[end - 1])

if __name__ == "__main__":
    main()

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

1. Считываем входные данные: количество вершин графа, матрицу смежности и номера начальной и конечной вершин.

2. Инициализируем массив distance для отслеживания расстояний до каждой вершины. Устанавливаем расстояние до начальной вершины равным 0, а до остальных вершин — равным -1 (значение -1 означает, что расстояние до вершины еще не определено).

3. Инициализируем очередь queue для обхода графа в ширину. Добавляем начальную вершину в очередь.

4. Используем поиск кратчайшего пути в графе в ширину (BFS). Итерируемся по вершинам, извлекая их из очереди.

5. Для каждой вершины проверяем все смежные вершины. Если граф связан с текущей вершиной и расстояние до смежной вершины еще не определено, то обновляем расстояние до смежной вершины и добавляем ее в очередь.

6. Поиск продолжается до тех пор, пока очередь не станет пустой.

7. Выводим длину кратчайшего пути до конечной вершины. Если расстояние до конечной вершины равно -1, то путь не существует.

Автор решения задачи: hdhai.com