Алгоритм Дейкстры

Алгоритм Дейкстры - алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. 

Если поиск в ширину позволяет найти путь с минимальным количеством пересадок из точки А в точку В, то алгоритм Дейкстры позволяет найти самый быстрый путь из точки А в точку В. 

Когда работаете с алгоритмом Дейкстры, с каждым ребром графа связывается число, называемое весом. Алгоритм Дейкстры работает с взвешенным графом и только с направленными ациклическими графами, которые нередко обозначаются сокращением DAG (Directed Acyclic Graph). Таким образом граф должен быть взвешенным, направленным и без циклов. 

Граф с весами называется взвешенным графом.

Граф без весов называется невзвешенным графом.

 

Для вычисления кратчайшего пути в невзвешенном графе используется поиск в ширину. Кратчайшие пути во взвешенном графе вычисляются по алгоритму Дейкстры.

Использование алгоритма Дейкстры с графом содержащим ребра с отрицательным весом, невозможно. Для этих целей используется алгоритм Беллмана-Форда.

Алгоритм Дейкстры состоит из четырех шагов:

1. Найти узел с наименьшей стоимостью (т.е узел, до которого можно добраться за минимальное время)

2. Обновить стоимости соседей этого узла.

3. Повторять, пока это не будет сделано дл всех узлов графа.

4. Вычислить итоговый путь.

 

Посмотрим как это выглядит в коде. Например, у нас будет такой граф:

Для реализации этого примера нам нужны три хеш-таблицы (ассоциативные массивы или словари): для графа, для родителей и для стоимостей.

Для представления графа со стоимостью перехода к соседу мы можем воспользоваться хеш-таблицей в хеш-таблице или многомерным ассоциативным массивом. 

graph = {}

graph['start'] = {}
graph['start']['a'] = 6
graph['start']['b'] = 2

graph['a'] = {}
graph['a']['end'] = 1

graph['b'] = {}
graph['b']['a'] = 3
graph['b']['end'] = 5

graph['end'] = {}

А для получения все соседей мы можем взять ключи:

print graph['start'].keys()

Хеш-таблицы для родителей и для хранения стоимостей:

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["end"] = infinity

parents = {}
parents['a'] = 'start'
parents['b'] = 'start'
parents['in'] = None

Массив для сохранения уже обработанных узлов:

processed = []

Алгоритм выглядит следующим образом:

Код:


# graph
graph = {}
# start node
graph['start'] = {}
graph['start']['a'] = 6
graph['start']['b'] = 2
# node a
graph['a'] = {}
graph['a']['end'] = 1
# node b
graph['b'] = {}
graph['b']['a'] = 3
graph['b']['end'] = 5
# node end
graph['end'] = {}

# costs
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["end"] = infinity

#parents
parents = {}
parents['a'] = 'start'
parents['b'] = 'start'
parents['in'] = None

# for processed items
processed = []

# function to get lowest
def find_lowest_cost_node (costs):
    lowest_cost = float("inf")
    lowest_cost_node = None

    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

# main code
node = find_lowest_cost_node(costs)
while node is not None:
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost:
            costs[n] = new_cost
            parents[n] = node
    processed.append(node)
    node = find_lowest_cost_node(costs)

# print parents
# print costs

 

https://habr.com/post/111361/

 

комментарии (26)

GeorgeRoomb GeorgeRoomb 2019-08-25 16:32:44
Когда идет трафик, то у тебя идут деньги. - - - - - - Ты уже начал получать трафик? http://sergievskiy-school.ru/PROMITEY_6in1 - - - - - - Если нет, то я не понимаю, почему ты хочешь пропустить этот важный процесс? Если у тебя нет трафика, то ты не сможешь начать зарабатывать из интернета достойные деньги. Я предлагаю тебе начать исправлять сейчас эту ситуацию. Узнай на этом онлайн вебинаре новые 30 способов получать трафик и зарабатывать от 200 000 руб. в месяц>> http://sergievskiy-school.ru/PROMITEY_6in1
GeorgeRoomb GeorgeRoomb 2019-09-02 02:54:56
Когда идет трафик, то у тебя идут деньги. - - - - - - Ты уже начал получать трафик? [url=http://sergievskiy-school.ru/PROMITEY_6in1]http://sergievskiy-school.ru/PROMITEY_6in1[/url] - - - - - - Если нет, то я не понимаю, почему ты хочешь пропустить этот важный процесс? Если у тебя нет трафика, то ты не сможешь начать зарабатывать из интернета достойные деньги. Я предлагаю тебе начать исправлять сейчас эту ситуацию. Узнай на этом онлайн вебинаре новые 30 способов получать трафик и зарабатывать от 200 000 руб. в месяц>> [url=http://sergievskiy-school.ru/PROMITEY_6in1]http://sergievskiy-school.ru/PROMITEY_6in1[/url]
GeorgeRoomb GeorgeRoomb 2019-09-03 04:41:29
Когда идет трафик, то у тебя идут деньги. - - - - - - Ты уже начал получать трафик? [url=http://sergievskiy-school.ru/PROMITEY_6in1]http://sergievskiy-school.ru/PROMITEY_6in1[/url] - - - - - - Если нет, то я не понимаю, почему ты хочешь пропустить этот важный процесс? Если у тебя нет трафика, то ты не сможешь начать зарабатывать из интернета достойные деньги. Я предлагаю тебе начать исправлять сейчас эту ситуацию. Узнай на этом онлайн вебинаре новые 30 способов получать трафик и зарабатывать от 200 000 руб. в месяц>> [url=http://sergievskiy-school.ru/PROMITEY_6in1]http://sergievskiy-school.ru/PROMITEY_6in1[/url]
Charlesdrold Charlesdrold 2020-06-06 14:55:44
Во время постройки посточнно требуется располагать на уме верного прораба по выборе правильных фурнитуру к тому же https://kfz-spb.ru/ незаменимых материалов с целью построении здания. У сегодняшних обстоятельствах таковым помощником возможно несомненно назвать строительный-магазин "КФЗ", намеренно исполненный под достаточно срочной и легкого покупки всяческих строевых-материалов через сайт. Страничка магазина <a href=https://kfz-spb.ru/>тыц</a> наличивает большое ассортимент продукции ото отечественных плюс зарубежных брендов, каковы пользователь можете сортировать у соотношении ото ценника и надобности, а магазин КФЗ сделает клиентам онлайн-консультацию от мастеров, гарант под оформленный товара, набор по поэтапности работ, отделочных изделий, стрехи, фасада к тому же местности из детальным описанием, ответами плюс заниженными ценниками. Приобрести также получить на дом Kfz-Spb.ru необходимые изделия полностью или же по розницу клиент сможет в онлайн строительном магазине, ну а мы разгрузит заказ неприменно к проверенному дом в Питере или Ленинградской району!
JeffreyNearl JeffreyNearl 2020-06-08 15:39:52
Ковер ручной изготовления есть основным из истинных компонентов комфортного плюс отличного эффекта у персонального помещения, который делает изумительный впечатление для истинных специалистов вкуса. Разработать на заявке дорожку ручной способом с возможностью индивидуальному картине покупатель можете через изготовителю «КараперПро» <a href=https://carpetpro.ru/catalog/kover-v-vannuy/>ковры для ванной</a> , мы реализовываем большой комплект ковров из 1400 открасок также высококачественных нитей: шелк, бамбук, льна, волос. По онлайн-магазине известного шоу-рума следует оценить сделанные проданные версии полотна, сложенные талантливыми художниками либо самому придумать цвет ширдака, задавая геометрическую форму, замеры, сырье потом оформить https://carpetpro.ru/ открытую расположение ткани у дизайне главной кабинета. «КараперПро» успешный в процессе двадцать двух десятков лет в LUXURY сегменте по изготовлению полотна на пол тонкой методики также имеет возможность сделать для Вас новый формат, сопутствуя пользователя на всех стедиях промышенности: консультирование, визуализация, заказ, ткань CarpetPro.ru затем пост чистка с гарантом. Оформить полотно ручной формата отличного характеристики можно только в «КараперПро».
Richardcef Richardcef 2020-06-19 01:58:57
<a href=https://androidinfo.ru/android-pomosch/611-kak-zakryt-profil-v-vk-s-telefona.html>закрытый профиль в вк</a>
Richardorill Richardorill 2020-10-05 01:18:06
По моему мнению Вы пошли ошибочным путём. ----- <a href=https://www.vidozahost.com/hannas-dairy-28-homemade-horny-wife-fuck-orgasm-and-creampie/>https://www.vidozahost.com/hannas-dairy-28-homemade-horny-wife-fuck-orgasm-and-creampie/</a> | https://www.vidozahost.com/
Thomashit Thomashit 2020-10-05 02:14:02
Я считаю, что Вы ошибаетесь. Могу отстоять свою позицию. Пишите мне в PM, поговорим. ----- <a href=https://www.threexvideo.com/cumming-in-mouth-compilation-oralendeavour-com/>https://www.threexvideo.com/cumming-in-mouth-compilation-oralendeavour-com/</a> | https://www.threexvideo.com/
WilliamScarf WilliamScarf 2020-10-05 02:48:21
Вы ошибаетесь. Пишите мне в PM, поговорим. ----- <a href=https://www.sexualcase.com/giant-tits-romanian-milf-fucked-hard/>https://www.sexualcase.com/giant-tits-romanian-milf-fucked-hard/</a> | https://www.sexualcase.com/
CharlesIrono CharlesIrono 2020-10-05 03:35:03
Я извиняюсь, но, по-моему, Вы не правы. Могу это доказать. Пишите мне в PM, поговорим. ----- <a href=https://www.masturporn.com/pervcity-colombian-anal-teen-izzy-lush/>https://www.masturporn.com/pervcity-colombian-anal-teen-izzy-lush/</a> | https://www.masturporn.com/
Larryfog Larryfog 2020-10-05 12:42:33
Это трудно сказать. ----- <a href=https://www.madhousedc.com/innocent-cheerleader-seduces-the-coach/>https://www.madhousedc.com/innocent-cheerleader-seduces-the-coach/</a> | https://www.madhousedc.com/
FrankLalse FrankLalse 2020-10-05 12:59:35
vя тоже так хочу научиться ----- <a href=https://www.daylyporn.com/cuckold-gloryhole-wife-and-husband-cumswapping/>https://www.daylyporn.com/cuckold-gloryhole-wife-and-husband-cumswapping/</a> | https://www.daylyporn.com/
MarcussoX MarcussoX 2020-10-07 21:54:01
Я извиняюсь, но, по-моему, Вы не правы. Давайте обсудим это. Пишите мне в PM, пообщаемся. ------ virtual phone number malaysia [url=https://virtual-local-numbers.com/countries/20-malaysia.html]https://virtual-local-numbers.com/countries/20-malaysia.html[/url] Извиняюсь, ничем не могу помочь, но уверен, что Вам помогут найти правильное решение. Не отчаивайтесь. ------ virtual phone number canada <a href=https://virtual-local-numbers.com/countries/7-canada.html>https://virtual-local-numbers.com/countries/7-canada.html</a> Конечно. Я присоединяюсь ко всему выше сказанному. Можем пообщаться на эту тему. ------ [url=https://smmchart.com/tiktok/views/]накрутка просмотров в тик ток[/url] Я извиняюсь, но, по-моему, Вы ошибаетесь. Давайте обсудим это. ------ [url=https://trefoil.tv/1441-cctv-3.html]https://trefoil.tv/1441-cctv-3.html[/url] Извините за то, что вмешиваюсь… Но мне очень близка эта тема. Готов помочь. ------ [url=https://partner.soc-proof.su/]https://partner.soc-proof.su/[/url] Я считаю, что Вы ошибаетесь. Предлагаю это обсудить. ------ [url=https://vacuumcleanerguru.com/shark-navigator-lift-away-professional-nv356e-review/]https://vacuumcleanerguru.com/shark-navigator-lift-away-professional-nv356e-review/[/url] Полезный вопрос ------ [url=https://joycasino-oficialniy-sayt.com/]https://joycasino-oficialniy-sayt.com/[/url]
Larryvef Larryvef 2020-10-07 22:19:39
Этого я не говорил. ------ buy us phone number <a href=https://virtual-local-numbers.com/countries/1297-usa-phone-number.html>https://virtual-local-numbers.com/countries/1297-usa-phone-number.html</a> | https://virtual-local-numbers.com
LeonardKic LeonardKic 2020-10-07 23:46:30
Ваша фраза великолепна ------ <a href=https://master-climat.com.ua/nastennye/>кондиционеры купить в киеве</a> | https://master-climat.com.ua
GregoryVex GregoryVex 2020-10-09 12:55:08
А другой вариант есть? ------ <a href=https://irongamers.ru/sale/keys/22229>общие аккаунты xbox 360 вк irongamers.ru</a> | https://irongamers.ru/
PatrickHok PatrickHok 2020-10-10 00:40:36
Какая фраза... супер, великолепная идея ------ [url=https://www.multipron.com/videos/hot-youtuber-shows-off-lingerie/]https://www.multipron.com/videos/hot-youtuber-shows-off-lingerie/[/url] | https://www.multipron.com/
Williamgow Williamgow 2020-10-23 18:38:29
Камни с натуральных пород располагают широкое использованием у различных отраслях, правда иногда же для большинства пользователей невразумительно, каким образом камни разделяются в дорогие либо полудрагоценные, как именно делают подделочные камни, какие именно находиться руды на огромному свету, и как из пород делают дорогостоящие ювелирка. Именно на текущем ресурсе <a href=https://akamni.ru/>списочек</a> Вы просмотрят объемную истинную публикации касательно типовые характеристики пород, сумеете увидить многогранность минералов нашей контингента, и разведаете у каковых областях https://akamni.ru/ свободно эксплуатируются камни. Указанные актуальные разделы по этому сайте проходят от квалифицированного мастера по области геологии- минералов, что открывает занимательными фактами об камни и их качествами, собственно потому у существующий знака зодиака есть соответственный ему AKamni.Ru минерал, каков будет несет внутреннюю профит и микротоки. Здесь читатели смогут узнать, как верно обходиться с камнями, чтобы они приносили личности здоровье и удачу.
RichardAlelt RichardAlelt 2020-10-23 20:03:28
Я извиняюсь, но, по-моему, Вы не правы. Пишите мне в PM, обсудим. ------ <a href=https://master-climat.com.ua/nastennye/cooper-hunter-nastennye/>Кондиционеры купер хантер</a> | https://master-climat.com.ua
Randalrig Randalrig 2020-10-28 18:34:15
Сейчас половина нашей жизнь реально работает на телефоне либо ноутбуке, потому очень следует сформировать под себя хорошие положение использования всех программ, какие сумеют намного http://adobeflashplayerfree.ru улучшить личные возможности. Первым из самых желанных модулей для качественного использования любых программ по личном устройстве есть подключение Adobe флеш плеер, тот что разрешает отобразить мультимедийные документ в всяком гаджете. Новую вариант всестороннего флеш плагина Adobe Flash плеер юзер имеет возможность установить совсем без оплаты на данном ресурсе <a href=http://adobeflashplayerfree.ru>adobe flash</a> под личного ПК, телефона или же айпада, программа подстроен существующую мозги устройства программу также поможет пользователю постановить вопросы с частоты загрузки, обработкой дубляжа, подготовка анимационных элементов также иные цели, те что демонстрируются в период включения. Последняя версия дает возможность Вам одержать огромный доступ до роликам также приложениям у сети, до тому же скачивание AdobeFlashPlayerFree.Ru этого плагина проходит очень быстро также вовсе не надо доп работы.
Randalrig Randalrig 2020-10-28 18:46:04
Теперь большая часть нашей с вами жизнь фактически отбивается по смартфоне или компьютере, потому достаточно необходимо организовать к себя комфортные обстановку установку современных приложений, каковы могут несравненно http://adobeflashplayerfree.ru усовершенствовать личные способности. Единым по очень востребованных плагинов под качественного использования различных форматов по вашем гаджете считается подключение adobe Flash Player, какой разрешает отобразить музыку файлы на любом источнику. Новую модификацию общего оперативного плагина Adobe флеш Player пользователь сумеет установить совсем без оплаты именно на нашем страничке <a href=http://adobeflashplayerfree.ru>вариантов</a> для вашего ноутбука, смартфона либо айпада, приложение поддерживает различную управление содержание и посодействует пользователю разрешить недоразумения с скорости прогрузки, изготовление дубляжа, разработка анимации плюс дополнительные альтернативы, те что происходят во время воссоздания. Обновленная формат дает возможность Вам эксплуатировать безусловный вход в фильмам также приложениям в сети интернет, до тому дополнительный плюс установка AdobeFlashPlayerFree.Ru презентованного плеера включается определенно быстро также не испытывает лишних работы.
JMilkye JMilkye 2020-11-09 18:30:03
Под всех фанатов аниме фильмов существует уникальный страничка, что навправил в библиотеке какие существующие файлы мультисериалов к тому же анимационных мультиков жанра Аниме, и охватывает большим интересом пользователей разных обозначенных категориях совершенно по всему городах. Платформа аниме вживую <a href=https://animenime.ru/anime-online/gintama-1-sezon>гинтама 1 сезон скачать</a> дозволяет своим пользователям осуществимость выделить аниме или же кино согласно годов публичного доступа, типажа, дубляжа, оценке и вбить желаемый транслейт и субтитры. Уже при дебютного визите аниме ресурса на первой окне пользователь сможете понять уровень достаточно известных аниме- сериалов также рассмотреть последние дополненные https://animenime.ru/ Аниме с обширным определением сути также откликом от настоящих аудитории. Мы обеспечили специальную шанс зарегистрированным зрителям готовить запрос аниме, каков гости не против посмотреть по нашем веб-портале, следует только верно AnimeNime.ru переключиться на вкладку заказов потом сделать личный сериал. Ресурс постоянно добавляем значительную коллекцию мультфильмов, потому уверенны, что наши посетители включат на нашем ресурсе собственно надобный фильм, какой пользователям доставит восторг!
Deges Deges 2020-11-12 14:04:48
<a href=https://0n0n.net/topic/196-kupit-pasport-rf-perekleika-pasporta-kupit-z/>купить загранник рф без предоплаты</a> | https://0n0n.net/
Deges Deges 2020-11-12 14:15:47
<a href=https://0n0n.net/topic/11429-pomosch-v-poluchenii-voennogo-bileta-kupit-voen/>где купить военный билет в москве</a> | https://0n0n.net/
Deges Deges 2020-11-12 14:22:16
<a href=https://0n0n.net/topic/11429-pomosch-v-poluchenii-voennogo-bileta-kupit-voen/>купить военный билет</a> | https://0n0n.net/
Deges Deges 2020-11-12 18:17:01
<a href=https://0n0n.net/topic/5995-bankovskie-karty-s-balansom/>кредитные карты с балансом цена</a> | https://0n0n.net/