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

Dijkstra находит shortest paths от source, когда все edge weights non-negative. Он повторно берет unsettled node с минимальной known distance и relaxes outgoing edges. Priority queue делает выбор efficient на sparse graphs.

Компромисс: сравните время, память и сложность реализации до выбора структуры или паттерна.

На интервью: Интервьюеры проверяют, отвергаете ли вы negative weights, храните ли distances отдельно от visited state и безопасно игнорируете stale queue entries.

Типовые ошибки: Plain BFS корректен только для unweighted или equal-weight graphs. Слишком ранний visited может зафиксировать non-final distance. Negative edges требуют другой algorithm.

Чеклист:

• Требуйте non-negative weights.
• Используйте min-priority queue.
• Делайте relax edges.
• Пропускайте stale distances.