Алгоритм дейкстры описание пошагово. Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе. Математическое описание алгоритма
Решить задачу о нахождении кратчайшего пути алгоритмом Дейкстры.
Найти кратчайший путь от Х0 до Х7. Граф задан элементами стоимостной матрицы
Построим этот граф
Начнем с элемента Х0 и присвоим ему метку 0, рассмотрим всех его соседей, т.к. там еще нет пометок, то присвоим им соответствующие длины:
Все соседи Х0 рассмотрены, помечаем ее и переходим к вершине Х1. ЕЕ соседи Х0, Х2,Х4, но Х0 помечена, не рассматриваем ее. Для Х2: 
, оставляем метку.
Для Х4: 
, заменяем метку. Все соседи вершины Х1 рассмотрены, помечаем ее
переходим к вершине Х2. ЕЕ соседи Х0, Х1,Х3, Х4, Х5, Х6, но Х0, Х1 помечены, не рассматриваем их.
Для Х3: 
, оставляем метку.
Для Х5: 
, заменяем метку.
Для Х4: 
, оставляем метку.
Для Х6: 
, заменяем метку.
Все соседи вершины Х2 рассмотрены, помечаем ее.
переходим к вершине Х3. ЕЕ соседи Х0, Х2, Х6, но Х0, Х2 помечены, не рассматриваем их.
Для Х6: 
, оставляем метку.
Все соседи вершины Х3 рассмотрены, помечаем ее.
переходим к вершине Х4. ЕЕ соседи Х1,Х2, Х5, Х7, но Х1, Х2 помечены, не рассматриваем их.
Для Х5: 
, заменяем метку.
Для Х7: 
, заменяем метку.
Все соседи вершины Х4 рассмотрены, помечаем ее.
переходим к вершине Х5. ЕЕ соседи Х2,Х4, Х6, Х7, но Х2, Х4 помечены, не рассматриваем их.
Для Х6: 
, оставляем метку.
Для Х7: 
, оставляем метку.
Все соседи вершины Х5 рассмотрены, помечаем ее.
переходим к вершине Х6. ЕЕ соседи Х2,Х3, Х5, Х7, но Х2, Х3, Х5 помечены, не рассматриваем их.
Для Х7: 
, оставляем метку.
Все соседи вершины Х6 рассмотрены, помечаем ее. И помечаем оставшуюся Х7, все вершины рассмотрены.
Вывод: Кратчайший путь их Х0 в Х7 имеет длину 101, этот путь: Х7-Х4-Х1-Х0.
Алгоримтм Демйкстры (Dijkstra"s algorithm) - алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. Известен также под названием "Сначала Кратчайший Путь" (Shortest Path First).
Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G = (V, E) с исходной вершиной s, в котором веса всех рёбер неотрицательны ((u, v) ? 0 для всех (u, v) E). В случае, когда ребра графа не равны, целесообразно использовать этот алгоритм.
Формулировка задачи. Имеется граф. Некоторая его вершина обозначена как вершина 1. Необходимо найти минимальные пути от вершины 1 до каждой из вершин графа. Минимальным путём будем называть путь с минимальной суммой цен вдоль пути. Ценой назовем неотрицательное число являющееся весом ребра.
Идея алгоритма. Идея основывается на следующем очевидном утверждении: Пусть построен минимальный путь из вершины а в вершину B. И пусть вершина B связана с некоторым количеством вершин i . Обозначим через C i - цену пути из вершины B в вершину i. Выберем из C i минимальную величину. Тогда минимальное продолжение пути из точки B пойдёт через выбранную величину.
Это утверждение действительно не требует доказательства. И из него вытекает очень серьёзное следствие. Пусть есть множество вершин через которые уже проходят минимальные пути. Такое множество гарантированно есть, это вершина 1. Утверждение сформулированное выше даёт возможность добавлять к уже существующему множеству вершин (будем далее называть их выделенными) еще одну вершину, а так как в графе количество вершин конечно, то за конечное количество шагов все вершины графа окажутся выделенными, а это и будет решением.
Сущность алгоритма Дейкстры и заключается в процедуре добавления еще одной вершины к множеству выделенных. Эта процедура состоит из двух шагов:
1. Строим множество вершин инцидентных выделенным и находим среди их вершину с наименьшей ценой. Найденная вершина добавляется в множество выделенных.
2. Строим множество вершин инцидентных выделенным и определяем для них новые цены. Новая цена вершины это минимальная цена пути от множества выделенных вершин до данной вершины. Строится новая цена так:
a. Для невыделенной вершины во множестве выделенных определяется подмножество вершин инцидентных данной.
b. Для каждой вершины выделенной подмножества определяется цена пути до данной.
c. Определяется минимальная цена. Эта цена и становится ценой вершины.
Алгоритм работает с двумя типами цен: ценой ребра и ценой вершины. Цены ребер являются постоянной величиной. Цены же вершин постоянно пересчитываются. Смысл этих цен различен. Цена ребра это цена перехода из вершины в вершину соединённую этим ребром. А цена вершины это цена минимального пути. Ещё одно важное замечание касается пересчета предварительных цен. Фактически, есть смысл пересчитывать предварительные цены только для тех вершин которые связаны с вершиной добавленной во множество выделенных на последнем шаге, так как для других вершин нет причин изменения предварительной цены.
Известно, что все цены (например, прокладки пути или проезда) неотрицательны. Найти наименьшую стоимость пути 1->i для всех i=1. n за время O (n2).
В процессе работы алгоритма некоторые города будут выделенными (в начале - только город 1, в конце - все). При этом:
для каждого выделенного города i хранится наименьшая стоимость пути 1->i; при этом известно, что минимум достигается на пути, проходящем только через выделенные города;
для каждого невыделенного города i хранится наименьшая стоимость пути 1->i, в котором в качестве промежуточных используются только выделенные города.
Множество выделенных городов расширяется на основании следующего замечания: если среди всех невыделенных городов взять тот, для которого хранимое число минимально, то это число является истинной наименьшей стоимостью. В самом деле, пусть есть более короткий путь. Рассмотрим первый невыделенный город на этом пути - уже до него путь длиннее! (Здесь существенна неотрицательность цен.)
Добавив выбранный город к выделенным, мы должны скорректировать информацию, хранимую для невыделенных городов. При этом достаточно учесть лишь пути, в которых новый город является последним пунктом пересадки, а это легко сделать, так как минимальную стоимость пути в новый город мы уже знаем.
Другими словами, каждой вершине из V сопоставим метку - минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово - на каждом шаге он "посещает" одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация. Метка самой вершины a полагается равной 0 , метки остальных вершин - бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае из еще не посещенных вершин выбирается вершина u , имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.
Поскольку алгоритм Дейкстры всякий раз выбирает для обработки вершины с наименьшей оценкой кратчайшего пути, можно сказать, что он относится к жадным алгоритмам.
Опишем более подробно схему работы алгоритма Дейкстры.
Алгоритм использует три массива из N (= числу вершин сети) чисел каждый. Первый массив A содержит метки с двумя значения: 0 (вершина еще не рассмотрена) и 1 (вершина уже рассмотрена); второй массив B содержит расстояния - текущие кратчайшие рас - стояния от до соответствующей вершины; третий массив с содержит номера вершин - k-й элемент С [k] есть номер предпоследней вершины на текущем кратчайшем пути из Vi в Vk. Матрица расстояний D задает длины дуге D ; если такой дуги нет, то D присваивается большое число Б, равное "машинной бесконечности".
Теперь можно описать:
1. (инициализация). В цикле от 1 до N заполнить нулями массив A; заполнить числом i массив C; перенести i-ю строку матрицы D в массив B, A [i]: =1; C [i]: =0 (i - номер стартовой вершины)
2. (общий шаг). Hайти минимум среди неотмеченных (т.е. тех k, для которых A [k] =0); пусть минимум достигается на индексе j, т.е. B [j] <=B [k] Затем выполняются следующие операции: A [j]: =1; если B [k] >B [j] +D , то (B [k]: =B [j] +D ; C [k]: =j) (Условие означает, что путь Vi. Vk длиннее, чем путь Vi. Vj Vk). (Если все A [k] отмечены, то длина пути от Vi до Vk равна B [k]. Теперь надо) перечислить вершины, входящие в кратчайший путь).
3. (выдача ответа). (Путь от Vi до Vk выдается в обратном порядке следующей процедурой:)
2. Выдать z;
3. z: =C [z]. Если z = О, то конец, иначе перейти к 3.2.
Для выполнения алгоритма нужно N раз просмотреть массив B из N элементов, т.е. алгоритм Дейкстры имеет квадратичную сложность: O (n2).
Ниже приведена блок-схема алгоритма Дейкстры (см. рис.2).
Рис.2. Блок-схема алгоритма Дейкстры
В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом (бомльшим максимального возможного пути в графе). Массив флагов заполняется нулями. Затем запускается основной цикл.
На каждом шаге цикла мы ищем вершину с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается когда флаги всех вершин становятся равны 1.
Рассмотрим пример нахождение кратчайшего пути. Дана сеть автомобильных дорог, соединяющих области города. Некоторые дороги односторонние. Найти кратчайшие пути от центра города до каждого города области.
Для решения указанной задачи можно использовать алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Работает только для графов без рёбер отрицательного веса.
Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.
Кружками обозначены вершины, линиями – пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначен их вес – длина пути. Рядом с каждой вершиной красным обозначена метка – длина кратчайшего пути в эту вершину из вершины 1.
Метка самой вершины 1 полагается равной 0, метки остальных вершин – недостижимо большое число (в идеале — бесконечность). Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.
Первый шаг
Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Обходим соседей вершины по очереди.
Первый сосед вершины 1 – вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2 (10000), поэтому новая метка 2-й вершины равна 7.
Аналогично находим длины пути для всех других соседей (вершины 3 и 6).
Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вершина 1 отмечается как посещенная.
Второй шаг
Шаг 1 алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.
Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.
Вершина 1 уже посещена. Следующий сосед вершины 2 - вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а 9 < 17, поэтому метка не меняется.
Ещё один сосед вершины 2 - вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна 22 (7 + 15 = 22). Поскольку 22<10000, устанавливаем метку вершины 4 равной 22.
Все соседи вершины 2 просмотрены, помечаем её как посещенную.
Третий шаг
Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим следующие результаты.
Четвертый шаг
Пятый шаг
Шестой шаг
Таким образом, кратчайшим путем из вершины 1 в вершину 5 будет путь через вершины 1 — 3 — 6 — 5
, поскольку таким путем мы набираем минимальный вес, равный 20.
Займемся выводом кратчайшего пути. Мы знаем длину пути для каждой вершины, и теперь будем рассматривать вершины с конца. Рассматриваем конечную вершину (в данном случае — вершина 5
), и для всех вершин, с которой она связана, находим длину пути, вычитая вес соответствующего ребра из длины пути конечной вершины.
Так, вершина 5
имеет длину пути 20
. Она связана с вершинами 6
и 4
.
Для вершины 6
получим вес 20 — 9 = 11 (совпал)
.
Для вершины 4
получим вес 20 — 6 = 14 (не совпал)
.
Если в результате мы получим значение, которое совпадает с длиной пути рассматриваемой вершины (в данном случае — вершина 6
), то именно из нее был осуществлен переход в конечную вершину. Отмечаем эту вершину на искомом пути.
Далее определяем ребро, через которое мы попали в вершину 6
. И так пока не дойдем до начала.
Если в результате такого обхода у нас на каком-то шаге совпадут значения для нескольких вершин, то можно взять любую из них — несколько путей будут иметь одинаковую длину.
Реализация алгоритма Дейкстры
Для хранения весов графа используется квадратная матрица. В заголовках строк и столбцов находятся вершины графа. А веса дуг графа размещаются во внутренних ячейках таблицы. Граф не содержит петель, поэтому на главной диагонали матрицы содержатся нулевые значения.
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 7 | 9 | 0 | 0 | 14 |
| 2 | 7 | 0 | 10 | 15 | 0 | 0 |
| 3 | 9 | 10 | 0 | 11 | 0 | 2 |
| 4 | 0 | 15 | 11 | 0 | 6 | 0 |
| 5 | 0 | 0 | 0 | 6 | 0 | 9 |
| 6 | 14 | 0 | 2 | 0 | 9 | 0 |
Реализация на C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#define
_CRT_SECURE_NO_WARNINGS
#include
#include
#define
SIZE 6
int
main()
{
int
a; // матрица связей
int
d; // минимальное расстояние
int
v; // посещенные вершины
int
temp, minindex, min;
int
begin_index = 0;
system("chcp 1251"
);
system("cls"
);
// Инициализация матрицы связей
for
(int
i = 0; i
a[i][i] = 0;
for
(int
j = i + 1; j
scanf("%d"
, &temp);
a[i][j] = temp;
a[j][i] = temp;
}
}
// Вывод матрицы связей
for
(int
i = 0; i
for
(int
j = 0; j
printf("\n"
);
}
//Инициализация вершин и расстояний
for
(int
i = 0; i
d[i] = 10000;
v[i] = 1;
}
d = 0;
// Шаг алгоритма
do
{
minindex = 10000;
min = 10000;
for
(int
i = 0; i
if
((v[i] == 1) && (d[i]
min = d[i];
minindex = i;
}
}
// Добавляем найденный минимальный вес
// к текущему весу вершины
// и сравниваем с текущим минимальным весом вершины
if
(minindex != 10000)
{
for
(int
i = 0; i
if
(a[i] > 0)
{
temp = min + a[i];
if
(temp < d[i])
{
d[i] = temp;
}
}
}
v = 0;
}
} while
(minindex < 10000);
// Вывод кратчайших расстояний до вершин
printf("\nКратчайшие расстояния до вершин: \n"
);
for
(int
i = 0; i
// Восстановление пути
int
ver; // массив посещенных вершин
int
end = 4; // индекс конечной вершины = 5 - 1
ver = end + 1; // начальный элемент - конечная вершина
int
k = 1; // индекс предыдущей вершины
int
weight = d; // вес конечной вершины
while
(end != begin_index) // пока не дошли до начальной вершины
{
for
(int
i = 0; i
if
(a[i] != 0) // если связь есть
{
int
temp = weight - a[i]; // определяем вес пути из предыдущей вершины
if
(temp == d[i]) // если вес совпал с рассчитанным
{ // значит из этой вершины и был переход
weight = temp; // сохраняем новый вес
end = i; // сохраняем предыдущую вершину
ver[k] = i + 1; // и записываем ее в массив
k++;
}
}
}
// Вывод пути (начальная вершина оказалась в конце массива из k элементов)
printf("\nВывод кратчайшего пути\n"
);
for
(int
i = k - 1; i >= 0; i--)
printf("%3d "
, ver[i]);
getchar(); getchar();
return
0;
}
Результат выполнения
Назад: Постановка задачи очень похожа на задачу, решаемую алгоритмом Форда-Беллмана: требуется найти кратчайший путь от выделенной вершины взвешенного графа (начальной) до всех остальных. Единственное отличие - теперь веса всех ребер неотрицательны.
Описание алгоритма
Разобьем все вершины на два множества: уже обработанные и еще нет. Изначально все вершины необработанные, и расстояния до всех вершин, кроме начальной, равны бесконечности, расстояние до начальной вершины равно 0.На каждой итерации из множества необработанных вершин берется вершина с минимальным расстоянием и обрабатывается: происходит релаксация всех ребер, из нее исходящих, после чего вершина помещается во множество уже обработанных вершин.
Напоминаю, что релаксация ребра (u, v), как и в алгоритме Форда-Беллмана, заключается в присваивании dist[v] = min(dist[v], dist[u] + w), где dist[v] - расстояние от начальной вершины до вершины v, а w - вес ребра из u в v.
Реализация
В самой простой реализации алгоритма Дейкстры нужно в начале каждой итерации пройтись по всем вершинам для того, чтобы выбрать вершину с минимальным расстоянием. Это достаточно долго, хотя и бывает оправдано в плотных графах, поэтому обычно для хранения расстояний до вершин используется какая-либо структура данных. Я буду использовать std::set, просто потому, что не знаю, как изменить элемент в std::priority_queue =)Также я предполагаю, что граф представлен в виде vector
Dijkstra
Доказательство корректности
Предположим, алгоритм был запущен на некотором графе из вершины u и выдал неверное значение расстояния для некоторых вершин, причем v - первая из таких вершин (первая в смысле порядка, в котором алгоритм выплевывал вершины). Пусть w - ее предок в кратчайшем пути из u в v.Заметим, что расстояние до w подсчитано верно по предположению
- Пусть найденное алгоритмом dist"[w] < dist[v]. Тогда рассмотрим последнюю релаксацию ребра, ведущего в v: (s, v). Расстояние до s было подсчитано верно, значит, существует путь из u в v веса dist[s] + w = dist"[v] < dist[v]. Противоречие
- Пусть найденное алгоритмом dist"[w] > dist[v]. Тогда рассмотрим момент обработки вершины w. В этот момент было релаксировано ребро (w, v), и, соответственно, текущая оценка расстояния до вершины v стала равной dist[v], а в ходе следующих релаксаций она не могла уменьшиться. Противоречие
Заметим, что если в графе были ребра отрицательного веса, то вершина w могла быть выплюнута позже, чем вершина v, соответственно, релаксация ребра (w, v) не производилась. Алгоритм Дейкстры работает только для графов без ребер отрицательного веса!
Сложность алгоритма
Вершины хранятся в некоторой структуре данных, поддерживающей операции изменения произвольного элемента и извлечения минимального.Каждая вершина извлекается ровно один раз, то есть, требуется O(V) извлечений.
В худшем случае, каждое ребро приводит к изменению одного элемента структуры, то есть, O(E) изменений.
Если вершины хранятся в простом массиве и для поиска минимума используется алгоритм линейного поиска, временная сложность алгоритма Дейкстры составляет O(V * V + E) = O(V²).
Если же используется очередь с приоритетами, реализованная на основе двоичной кучи (или на основе set), то мы получаем O(V log V + E log E) = O(E log V).
Если же очередь с приоритетами была реализована на основе кучи Фибоначчи, получается наилучшая оценка сложности O(V log V + E).
Но при чем же здесь задача с собеседования в Twitter?
Задачу с самого собеседования решать не очень интересно, поэтому я предлагаю ее усложнить. Перед дальнейшим чтением статьи я рекомендую ознакомиться с оригинальной постановкой задачиНовая постановка задачи с собеседования
- Назовем задачу с собеседования «одномерной». Тогда в k-мерном аналоге будут столбики, пронумерованные k числами, для каждого из которых известна высота. Вода может стекать со столбика в соседний столбик меньшей высоты, либо за край.
- Что такое «соседние столбики»? Пусть у каждого столбика есть свой список соседей, какой угодно. Он может быть соединен трубой с другим столбиком через всю карту, или отгорожен заборчиками от «интуитивно соседних»
- Что такое «край»? Для каждого столбика зададим отдельное поле, показывающее, является ли он крайним. Может, у нас дырка в середине поля?
Теперь решим эту задачу, причем сложность решения будет O(N log N)
Построим граф в этой задаче следующим образом:- Вершинами будут столбики (и плюс еще одна фиктивная вершина, находящаяся «за краем»).
- Две вершины будут соединены ребром, если в нашей системе они соседние (или если одна из этих вершин - «край», в другая - крайний столбик)
- Вес ребра будет равен максимуму из высот двух столбиков, которые он соединяет
Теперь все встает на свои места: для того, чтобы попасть за край из некоторого центрального столбика, нужно пройти по некоторому пути (по которому вода и будет стекать), причем максимальная из высот столбиков этого пути в лучшем случае как раз совпадет с «расстоянием» от начального столбика до «края» (или, поскольку граф не является ориентированным, от «края» до начального столбика). Осталось лишь применить алгоритм Дейкстры.
Реализация
void Dijkstra(int v)
{
// Инициализация
int n = (int)edges.size();
dist.assign(n, INF);
dist[v] = 0;
set
Но это же сложнее и дольше, чем оригинальное решение! Кому это вообще нужно?!
Обращаю Ваше внимание, что мы решали задачу в общем виде. Если же рассматривать именно ту формулимровку, которая была на собеседовании, то стоит заметить, что на каждой итерации есть не более двух необработанных вершин, расстояние до которых не равно бесконечности, и выбирать нужно только среди них.Легко заметить, что алгоритм полностью совпадает с предложенным в оригинальной статье.
Была ли эта задача хорошей?
Я думаю, эта задача хорошо подходит для объяснения алгоритма Дейкстры. Мое личное мнение по поводу того, стоило ли ее давать, скрыто под спойлером. Если Вы не хотите его видеть - не открывайте.Скрытый текст
Если человек хоть немного разбирается в графах, он точно знает алгоритм Дейкстры - он один из самых первых и простых. Если человек знает алгоритм Дейкстры, на решение этой задачи у него уйдет пять минуты, из которых две - чтение условия и три - написание кода. Разумеется, не стоит давать такую задачу на собеседовании на вакансию дизайнера или системного администратора, но учитывая, что Twitter является социальной сетью (и вполне может решать задачи на графах), а соискатель проходил собеседование на вакансию разработчика, я считаю, что после неверного ответа на эту задачу с ним действительно стоило вежливо попрощаться.
Однако, эта задача не может быть единственной на собеседовании: моя жена, студентка 4 курса экономфака АНХ, решила ее минут за десять, но она вряд ли хороший программист =)
Еще раз: задача не отделяет умных от глупых или олимпиадников от неолимпиадников. Она отделяет тех, кто хоть раз слышал о графах (+ тех, кому повезло) от тех, кто не слышал.
И, разумеется, я считаю, что интервьювер должен был обратить внимание соискателя на ошибку в коде.