Как стать автором
Обновить
43
0
Алексей Кузьмин @alexeykuzmin0

Пользователь

Отправить сообщение

Графы для самых маленьких: Dijkstra или как я не ходил на собеседование в Twitter

Время на прочтение 6 мин
Количество просмотров 105K
Не так давно наткнулся на статью о том, как Michael Kozakov не смог решить алгоритмическую задачу на собеседовании в Twitter. Решение этой задачи — почти в чистом виде один из самых стандартных алгоритмов на графах, а именно, алгоритм Дейкстры.
В этой статье я постараюсь рассказать алгоритм Дейкстры на примере решения этой задачи в несколько усложненном виде. Всех, кому интересно, прошу под кат.
Читать дальше →
Всего голосов 67: ↑56 и ↓11 +45
Комментарии 16

Графы для самых маленьких: Ford & Bellman или как понять, что ты попал в бесконечно далекое прошлое

Время на прочтение 3 мин
Количество просмотров 59K
В предыдущих частях цикла мы рассмотрели алгоритмы DFS и BFS, позволяющие найти путь в графе и обладающие рядом других интересных свойств. Но в жизни очень часто оказывается, что гораздо проще выглядит модель задачи в виде графа с неодинаковыми длинами ребер. Поиском кратчайшего пути во взвешенном графе мы и займемся под катом.
Читать дальше →
Всего голосов 30: ↑27 и ↓3 +24
Комментарии 5

Графы для самых маленьких: BFS 0-1

Время на прочтение 2 мин
Количество просмотров 25K
Добрый день, уважаемые хабровчане!
В предыдущих постах уже рассказывалось о двух алгоритмах, с помощью которых можно найти путь сквозь лабиринт: DFS и BFS. Всех, кто хочет еще немного поиздеваться над нашим лабиринтом, прошу под кат.
Читать дальше →
Всего голосов 10: ↑8 и ↓2 +6
Комментарии 3

Графы для самых маленьких: BFS

Время на прочтение 3 мин
Количество просмотров 102K
В предыдущем посте рассказывалось об обходе графа в глубину. Сегодня я бы хотел рассказать о не менее важном алгоритме теории графов — об обходе в ширину.
В прошлый раз мы уже научились искать какой-нибудь путь сквозь лабиринт. Всех желающих найти кратчайший путь прошу под кат.
Читать дальше →
Всего голосов 35: ↑26 и ↓9 +17
Комментарии 2

Графы для самых маленьких: DFS

Время на прочтение 3 мин
Количество просмотров 178K
В этой статье хотелось бы рассказать об одном из самых распространенных алгоритмов на графах — об обходе в глубину — на примере решения задачи о нахождении пути сквозь лабиринт. Всем, кому это интересно — добро пожаловать под кат!

Читать дальше →
Всего голосов 36: ↑28 и ↓8 +20
Комментарии 39

Информация

В рейтинге
Не участвует
Откуда
Москва, Москва и Московская обл., Россия
Зарегистрирован
Активность