Pull to refresh
43
0
Алексей Кузьмин @alexeykuzmin0

User

Send message

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

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

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

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

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

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

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

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

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

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

Читать дальше →
Total votes 36: ↑28 and ↓8 +20
Comments 39

Information

Rating
Does not participate
Location
Москва, Москва и Московская обл., Россия
Registered
Activity