Название «алгоритм Дейкстры» звучит для многих выпускников как что-то из университетского курса по продвинутым структурам данных, требующее серьёзной олимпиадной подготовки. Увидев подобную задачу в варианте ЕГЭ, ученик решает, что она точно недоступна без специальной углублённой подготовки, и пропускает её, даже не пытаясь разобраться. Алгоритм Дейкстры на ЕГЭ по информатике на уровне школьной программы требует не написания кода с нуля, а понимания одной пошаговой процедуры поиска кратчайшего пути в графе, которую вполне реально освоить за пару занятий...

Задачи на графы встречаются в ЕГЭ по информатике в разных форматах: в заданиях на маршруты, таблицы, схемы и анализ связей. Многие ученики их боятся, потому что слово «граф» звучит страшно и ассоциируется с чем-то из университетской математики. На деле большинство задач ЕГЭ на графы решаются одним методом — и когда он освоен, задача становится почти механической. Граф — это набор вершин (точек) и рёбер (связей между точками). Всё. Никакой магии. Когда вы рисуете схему городов с дорогами между ними, или рисуете связи между людьми в социальной сети — вы рисуете граф...