⚙️ Алгоритмы  ·  20 вопросов  ·  ~45 мин  ·  ⏱ Таймер 45:00  ·  Сложный  · 

Кратчайшие пути

Кратчайший путь определяется не числом строк алгоритма, а моделью весов. BFS работает на единичных рёбрах, Дейкстра — на неотрицательных, Беллман—Форд выдерживает отрицательные рёбра и обнаруживает опасные циклы. Тест требует трассировать релаксации, находить неверную «раннюю пометку» и восстанавливать маршрут.

Отвечено: 0 из 20
⏱ --:--
0%
💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 45 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.
Вопрос 1 из 20
Какое расстояние получит вершина 4?
Python
from collections import deque
g = [[1,2], [3], [3,4], [4], []]
dist = [-1] * 5
dist[0] = 0
q = deque([0])
while q:
    v = q.popleft()
    for u in g[v]:
        if dist[u] == -1:
            dist[u] = dist[v] + 1
            q.append(u)
print(dist[4])
Вопрос 2 из 20
Что означает начальная очередь из нескольких источников?
Python
sources = [1, 5, 8]
for s in sources:
    dist[s] = 0
    q.append(s)
Вопрос 3 из 20
В графе без весов длина пути обычно равна:
Вопрос 4 из 20
Какой алгоритм нужен для клетки с состоянием «ключ уже взят или нет»?
Python
from collections import deque

start = (start_row, start_col, False)
queue = deque([start])
visited = {start}
while queue:
    row, col, has_key = queue.popleft()
    for nr, nc in neighbours(row, col):
        next_has_key = has_key or grid[nr][nc] == 'K'
        # Дверь D разрешена только при next_has_key == True.
        # Нужно выбрать, что считать отдельной вершиной поиска.
Вопрос 5 из 20
Почему DFS не гарантирует кратчайший путь в невзвешенном графе?
Вопрос 6 из 20
Какое расстояние до вершины 3?
Python
# рёбра: 0->1 (5), 0->2 (2), 2->1 (1), 1->3 (3), 2->3 (10)
import heapq
g = [[(1,5),(2,2)], [(3,3)], [(1,1),(3,10)], []]
dist = [float('inf')] * 4
dist[0] = 0
heap = [(0,0)]
while heap:
    d,v = heapq.heappop(heap)
    if d != dist[v]: continue
    for u,w in g[v]:
        nd = d+w
        if nd < dist[u]:
            dist[u] = nd
            heapq.heappush(heap,(nd,u))
print(dist[3])
Вопрос 7 из 20
Какая запись станет устаревшей?
Python
from heapq import heappush, heappop

best = [0, 9, 3]
heap = [(3, 2), (9, 1)]

# После обработки вершины 2 найден более короткий путь к 1:
best[1] = 4
heappush(heap, (4, 1))

# При извлечении запись сравнивают с best[vertex].
Вопрос 8 из 20
Почему после извлечения актуальной минимальной вершины её расстояние окончательно при неотрицательных весах?
Вопрос 9 из 20
Что неверно в реализации?
Python
dist[start] = 0
heap = [(0, start)]
seen = {start}
while heap:
    d, v = heappop(heap)
    for u, w in g[v]:
        if u not in seen:
            seen.add(u)
            dist[u] = d + w
            heappush(heap, (dist[u], u))
Вопрос 10 из 20
Какова сложность Дейкстры со списками смежности и бинарной кучей без отдельной операции уменьшения ключа?
O((V+E)\log V)
Вопрос 11 из 20
Почему классическая реализация Дейкстры, которая после извлечения считает вершину окончательно обработанной и больше не улучшает её расстояние, ошибётся на этом графе?
Python
graph = {
    0: [(1, 2), (2, 5)],
    1: [],
    2: [(1, -10)],
}

# Вершина 1 извлекается с меткой 2 и попадает в closed.
# Рёбра, ведущие в closed, реализация больше не релаксирует.
Вопрос 12 из 20
Сколько полных проходов релаксации достаточно в Беллмане—Форде без отрицательного цикла?
V-1
Python
distance = [float('inf')] * V
distance[source] = 0

for _ in range(number_of_full_passes):
    changed = False
    for u, v, weight in edges:
        if distance[u] + weight < distance[v]:
            distance[v] = distance[u] + weight
            changed = True
    if not changed:
        break
Вопрос 13 из 20
Что означает улучшение расстояния на V-м проходе Беллмана—Форда?
Вопрос 14 из 20
Есть ли отрицательный цикл?
Python
# цикл 1->2 вес 3, 2->3 вес -5, 3->1 вес 1
total = 3 - 5 + 1
print(total)
Вопрос 15 из 20
Можно ли иметь отрицательные рёбра без отрицательных циклов и корректные конечные кратчайшие пути?
Вопрос 16 из 20
Какой путь восстановится?
Python
parent = [-1, 0, 0, 1, 3]
target = 4
path = []
v = target
while v != -1:
    path.append(v)
    v = parent[v]
path.reverse()
print(path)
Вопрос 17 из 20
Какое присваивание нужно выполнить при успешной релаксации ребра v→u?
Python
nd = dist[v] + w
if nd < dist[u]:
    dist[u] = nd
    # ...
Вопрос 18 из 20
Что означает parent[target] = -1, если target не является источником?
Вопрос 19 из 20
Почему этот цикл может зациклиться?
Python
path = []
v = target
while v != source:
    path.append(v)
    v = parent[v]
Вопрос 20 из 20
Если существуют несколько кратчайших путей одинаковой длины, что хранит обычный массив parent?
dist[u]+w(u,v)=dist[v]

Ответьте на все 20 вопросов, чтобы получить результат

🔗 Встроить тест на свой сайт (iframe) ▼

Скопируйте код и вставьте в любое место на вашем сайте:

Также доступна прямая ссылка на embed-страницу