Пути и сети: Дейкстра, Беллман — Форд, Флойд — Уоршелл, A*, остовные деревья, потоки — авторское изложение

ru · official · sha256:bde5792c83e94d1193746da240273c54b27340d9a9305ed6599493d8bbef2a3cRU

§1. Веса, релаксация, разрез и остаточная сеть Взвешенный граф — граф, каждому ребру которого приписано число, называемое весом. Длина пути есть сумма весов его рёбер. Кратчайший путь между двумя вершинами — путь наименьшей длины; при наличии цикла отрицательного веса, достижимого из начала и достигающего конца, кратчайшего пути не существует вовсе, потому что длину можно уменьшать неограниченно. Оценка расстояния до вершины — верхняя граница длины кратчайшего пути, поддерживаемая описанием. Релаксация ребра из u в v есть замена оценки для v суммой оценки для u и веса ребра, если эта сумма меньше. Все четыре описания кратчайших путей суть разные порядки релаксации, и различие между ними — именно в порядке. Свойство оптимальной подструктуры: всякий начальный отрезок кратчайшего пути сам является кратчайшим путём. На нём стоят все четыре описания; без него релаксация не имела бы смысла. Разрез графа — разбиение множества вершин на две непустые части. Ребро пересекает разрез, когда его концы лежат в разных частях. Правило разреза: для всякого разреза ребро наименьшего веса среди пересекающих его входит в некоторое минимальное остовное дерево. Оба описания остовного дерева суть разные способы выбирать такие рёбра, и оба опираются на это одно правило. Сеть — ориентированный граф с неотрицательными пропускными способностями рёбер, выделенными истоком и стоком. Поток — приписывание рёбрам чисел, не превосходящих пропускных способностей, при котором для всякой вершины, кроме истока и стока, сумма входящего равна сумме исходящего. Величина потока — суммарный исходящий поток истока. Остаточная сеть при данном потоке содержит для каждого ребра прямое остаточное ребро с пропускной способностью, равной неиспользованной части, и ОБРАТНОЕ остаточное ребро с пропускной способностью, равной уже пущенному потоку. Обратные рёбра существенны: без них поток нельзя было бы перенаправить, и метод дополняющих путей был бы неверен, а не медленен. Дополняющий путь — путь из истока в сток по рёбрам остаточной сети с положительной пропускной способностью. Теорема о максимальном потоке и минимальном разрезе: величина максимального потока равна наименьшей суммарной пропускной способности разреза, отделяющего исток от стока; поток максимален тогда и только тогда, когда дополняющего пути нет.

Referencing norms: AnswersHere, f-0abd0722405d41b014f8721f, f-0e6e06d7f562176900d165e3, f-1318d3de7ba5a530dfdd6539, f-14740fd6ead8767a86680243, f-157231309f3e344e5d0c9104, f-1906c6fd5523f896ee2d57e5, f-1a9ea68517b4c2c74f3afbc0, f-1ecacb4e35b2790e60622dd6, f-28413879a25983fc50e1b465, f-331d103ec360ee5d7ea6edad, f-34ef96b9a68fa904a3ce865c, f-370bb0da0c6b1aeed5747a1f, f-46d3cafb274737cf2941ef37, f-4d0fd3d20e7a837e1651adf3, f-51c9c74638361bc8d9a14f9c, f-52ec556855ad00ec64167194, f-57aa14b7df9bb45aa6e575d5, f-595dca3b4582f91fb1fe430f, f-5b7ecf902c2d026c299e42d3, f-5d7a1307c97c6cc4cd3bf50e, f-5dec186f5b326a4a1c0368f5, f-5e4f90674145d77588c056a9, f-6326bf9311eb3c7089f4c732, f-65838a61359c84aea2d6a586, f-69f86138460b704821842bd8, f-6bd79511c60e3840778114c1, f-6e581887a3c86991ac6e57d2, f-71293e9fecc7897a55d5bd44, f-7612b7bdf3098a0d3b1018ea, f-866048dfc0845d24dfd3af50, f-880942c32c7ec86cad203be8, f-891ebd270091b387f6a9dd55, f-95f71f20cdda264ac9df2c40, f-9b874c261a4364e933fcf109, f-9dac4bbb1420847aa2734d57, f-b31760e18dd058ec44da636b, f-c0ca9b1d06525df2c5011ab1, f-c5d1f5e60a07db759dff8610, f-d65a5d14b610e872f0441534, f-ddb3e17fe9f240ff08047b47, f-e0d9e441cb95389768e39ae0, f-e52c557942b060aea732e336, f-eda028b4652770c75dbe1233, f-ede8eb0e42d6286f370432d4, f-f2ad71e5580241a0c57a7713, f-f3a5fe571f830776a730bed0, f-fc2c9a013f5b19f2ac21383f

ru · official · sha256:ad3677cc2f8f807115697f8469b471668be0b4dcd54aba4db3190deb4ad46868RU

§2. Алгоритм Дейкстры Задача: по сети с НЕОТРИЦАТЕЛЬНЫМИ весами и начальной вершине получить длины кратчайших путей до всех вершин. Вариант — с приоритетной очередью, извлечением вершины наименьшей оценки и однократной её обработкой. Оценка начальной вершины полагается нулём, остальных — бесконечностью. Пока очередь непуста, извлекается вершина наименьшей оценки; если она уже обработана, извлечение пропускается. Иначе вершина объявляется обработанной, и все исходящие из неё рёбра релаксируются; вершина с уменьшившейся оценкой помещается в очередь. Основание корректности — неотрицательность весов: извлечённая вершина наименьшей оценки не может получить меньшую оценку позже, потому что любой другой путь до неё проходит через вершину с не меньшей оценкой и добавляет неотрицательную длину. Именно здесь и ломается описание при отрицательных весах: утверждение перестаёт быть верным, и вершина обрабатывается преждевременно. Отрицательный вес есть нарушение ПРЕДУСЛОВИЯ, а не источник медленной работы. Описание при таком входе не определено, и это надо говорить прямо. Инвариант: оценка каждой обработанной вершины равна длине кратчайшего пути до неё, а оценка необработанной равна длине кратчайшего пути, все промежуточные вершины которого обработаны. Оценка: при двоичной куче время порядка суммы числа рёбер и числа вершин, умноженной на логарифм числа вершин. Ленивое удаление, при котором устаревшие записи очереди пропускаются, выбрано изложением ради простоты; вариант с уменьшением ключа даёт ту же оценку иным устройством.

Referencing norms: f-0289038db3fb00c3e8ee8b57, f-037b8b5de65adb204cc69ea1, f-076f65dbdce0443882d32d4b, f-097ea576adb7d93ae66fa32b, f-140d044d1331e2acab8837c5, f-180cdf25c9f252983dc2cdd4, f-18ffb46273da8fdaccee4c9c, f-1d22d8e488d7c58fffc09722, f-20f8cd7d1047e55c435fc787, f-26c556a0551a49aa245df496, f-296a1a3bc439f3859976c82a, f-29ba6e78115ee72d9aec0649, f-2bb309e96777a5ff4ad1b9bb, f-32ef29b2c7869cf25df8a40f, f-34e67b5531ec72157b74a187, f-37ccc66f6d9ea301bf31a163, f-3ad1d34e589c9e0cee622be5, f-3e3a31eb475edfc61eadc021, f-4162465a5ee734d592cd93d3, f-448c7a9e145f4abe482b7d9c, f-44e9a5926adb81b6e349e2d4, f-451006a93b0dea477606ccda, f-479cefd59b184e9246c1ecbf, f-4b136475b30fbe85a1241eb9, f-4ecead75d89ccaa8d1196989, f-4f0c3d1557907ea3459bfa96, f-4f35ce4c8e07bff504cbc34a, f-5a78de85e540e21d4b88fc72, f-5bcf827468df24440c24af01, f-5d7ab66c94a14f30b3095c77, f-5fbe8602eeaedded77ee9668, f-6183c8fcdccc16a26a928e06, f-62869b1f95ec33f00b5a620a, f-6783598eca805ce96724907e, f-716b6156191931eb098e9b88, f-788f9b3d82bb822444e2503f, f-79485fef2cbfdb0bd57d12f7, f-7a8ed3ff591c04b31991457b, f-812eed059b92a33ef4cbed01, f-842c86a04ba63875f1079353, f-8a3244690a3c8506c101c9e5, f-8a9ffff500d88a0a60508c2d, f-8c2b60224f125afabc0f53d8, f-910b89756bb5dd9d5eff73d0, f-92306e56ade7b1899140e051, f-958492c822521395d2b17bd9, f-99e1df73bf4ce39497cb9b1b, f-9a6fabe9656417ca4df1525d, f-9af89604feb011228f777b3b, f-9cfb8133abde411897014a5d, f-9dbb164bdc3c71aeea533bb4, f-a25f352af87e722283a72e16, f-a5f79d0e5a0bd0587384f1ae, f-ad4ab5567abc9bb750b46a4d, f-b0768a49ebfd64edfb711c0e, f-b135481ebfcad4da4d494713, f-b6e8b8d25c9580842990807b, f-baec1571ac6e6c8b43d21afc, f-be5bec75b3f4970bb4489790, f-c083dc9dd0305b3469da9ce6, f-c74055566748058eeba69a14, f-c88776c4a5a0a18f878cef41, f-cf6b72bf99356626a14cd8f0, f-cf7a29fcdc2af5c25b69da76, f-cf901d1cd683cda37d477095, f-d2e46cb31d2f3ff1bcb58cff, f-d2e4e63b94c3cd79ad4cacfd, f-d386c344ad71ce018fb93148, f-d69c95f5937eda2716532af4, f-d73788e73f52118c54f2e6ac, f-d8636c30659ac71a616f5261, f-db5e6eaef7a94eb6e08a4ec7, f-db7fa4416d5d62fe75bf37b5, f-dc1223087a0796606636d2a6, f-dd7a4460207c29fcab2076ff, f-e2801c41d6a207f9819f10e2, f-e2965f8c810f22c1e9e4c139, f-e2d6386f1ffe5d23c8e3cfb2, f-e43da209a6f9d950cccf2fed, f-e853b55498872260704faaec, f-e8fe3c639872bc46dc35f428, f-efe2e32a0dcc848963072a9a, f-f8d094c8c33af04f90d3d1ae, f-f924de92b0c215f9b53850ac, f-fb2dddefc6cb80c3d322c889

ru · official · sha256:8260ec6f98ac8ce868a6accaff04651b4f2195fa741b8624d036ccb601d11f44RU

§3. Алгоритм Беллмана — Форда Задача: по сети с ПРОИЗВОЛЬНЫМИ весами и начальной вершине получить длины кратчайших путей либо обнаружить достижимый цикл отрицательного веса. Вариант — с V − 1 полными проходами релаксации и одним контрольным проходом. Все рёбра релаксируются подряд, и такой проход повторяется V − 1 раз. Затем выполняется ещё один проход: если хоть одно ребро всё ещё релаксируется, в графе есть достижимый цикл отрицательного веса. Основание числа проходов: кратчайший путь без циклов содержит не более V − 1 рёбер, а после k проходов верны все оценки для путей длиной не более k рёбер. Отсюда V − 1 проходов достаточно, и это не запас, а точная граница. Контрольный проход есть не проверка на всякий случай, а часть описания: без него результат на графе с отрицательным циклом бессмыслен, и описание молчит об этом. Инвариант: после k проходов оценка каждой вершины не превосходит длины кратчайшего пути до неё, содержащего не более k рёбер. Оценка: время порядка произведения числа вершин на число рёбер. Она хуже, чем у Дейкстры, и это плата за допущение отрицательных весов. Досрочный выход при проходе без единой релаксации допустим и оценки не меняет; это уточнение варианта, а не другой алгоритм.

Referencing norms: f-03079f1b9cc7a1b9aa53fe73, f-0487fd1e6428f41cf22c5951, f-0e3cd691a3d5de844c177f6a, f-169d4e3af0736cf24bf22516, f-18061bbd674bf8a4bd450f42, f-194413082fb702e6bd7efffc, f-19ad5f8cd5f7589737dba632, f-1a21f524d3ef5a9b7c78ed2b, f-1e5b55aec2145e8619a43208, f-2781c23b589931c8f49f39cb, f-29e559682620da21e1865ada, f-2dc65ed3fcbbaaf560992d3d, f-310dab3b941fc7cbcac5f136, f-3216cfadb5820d4d4dec4a54, f-369de52dafa167c7435d32d8, f-36f612725c7701a4f599a81b, f-46b024c224caef0db70b607c, f-481cc204a1146c6d8c46ac53, f-4e5f7d1a4df801dd96815c31, f-4e8908f7ec1b800b3704a51b, f-4f8db29a5cced24e4f0ef775, f-4fbc0dff0bf47f8ece6e3ed8, f-50b0519d08e14774c344e694, f-549786336f0226a33da46672, f-5c0ce29473ac92de5bd51c1a, f-61270df6e7b79687134e6c2a, f-64511dfeb9348d8d07717f92, f-6496e6e6f6796bb8d5bb440e, f-67d87b34e2898df9fd86da99, f-6b73b8c56358541bc981e82e, f-6e7a5ae4a69c43a11dc24201, f-6fdb0f7530f157c93215b4ad, f-7060aa85f549b892b471513e, f-73dbcddebc7f8907466e5ec5, f-7bbf34ae4fcfc0d632d54344, f-7c9cdce9092497ad7f3d838b, f-7d726419cec75748ae15428f, f-857b1c786e56445929afd8ce, f-8750eda08ca30389de58eff3, f-883a35e9ce296c6de09dd600, f-89021073808fa7fcdee6e096, f-89ff8542f74013343f502f9c, f-94fd94a04967206fb9dc9229, f-95e1091e6cb9ac0c2abf5fcc, f-9ade5d74af02c04a95217cf7, f-9d0ad8b346c57fe3aaa5b467, f-9d2e9eb89c9dce69a541afb2, f-9dcf3b47cfa92a4cc40af4d0, f-9e3efbb068b4bd1322677a51, f-9fea9a816d9ce5851e76dbaf, f-a1b80ce7464ca8dc7c0be7d1, f-a7b05cf7f02e94857f3cf8f2, f-ae05a2f4e73d8f6e29bfce47, f-b0f789f95c80c3a5e983bf22, f-b1ca5169d8e09115fcbfac25, f-b41660d6523d4a29cf607849, f-b437c34997bfd53c6de9ac6f, f-b9549ddaff82e051b4110f08, f-bad282e401be3eeb554bb42b, f-bda6342b7e85c74d15d80753, f-c12eac3fa614e7c6ceeb9ad6, f-c366c93317da092d414dd5e1, f-c3868d11aca5845388c81c17, f-ca313c372400dea769778481, f-ca88234958ae377b936a91f9, f-cbfdc7cdbafba92473310f13, f-cef861ec4196ed3b0601d5ee, f-cfac5ae2d320f5e465bbc893, f-d918391d5c758797eb305a85, f-d96507728ed119063ae9b386, f-dd97d9fd3a2165b68466e284, f-e645831d8374313595f7c41b, f-eb4dcf4f21e14134e6b63534, f-eee633ce2d4f790471f4273c, f-f0a90ce5ab2635c7d2986866, f-f316fb772955c3223aa60ee2, f-f55187d1846dbcd01066d6b1, f-f6234534239675ec97118fac, f-fca15817ee341c21ec39f5ea, f-fd396003dcf7a721e6c12c6b

ru · official · sha256:8bd7cbdcd9d62670047c7d0e68f587a07bf9a0791be2e3a559886b1b1563a4a1RU

§4. Алгоритм Флойда — Уоршелла Задача: по сети с произвольными весами получить длины кратчайших путей между ВСЕМИ парами вершин. Вариант — тройной цикл с внешним циклом по промежуточной вершине. Заводится таблица расстояний, изначально равная весам рёбер, нулю на диагонали и бесконечности в остальных местах. Затем для каждой промежуточной вершины k и каждой пары (i, j) расстояние заменяется меньшим из текущего и суммы расстояний через k. Порядок циклов существен: внешним обязан быть цикл по промежуточной вершине k. Иной порядок даёт неверный результат, и это самая частая ошибка изложений. Инвариант: после обработки первых k промежуточных вершин таблица содержит длины кратчайших путей, все промежуточные вершины которых лежат среди первых k. Отрицательные циклы обнаруживаются по отрицательному значению на диагонали: если расстояние из вершины в саму себя стало отрицательным, вершина лежит на цикле отрицательного веса. Оценка: время порядка куба числа вершин, память порядка квадрата. Вариант выгоден на плотных графах и тогда, когда нужны все пары; для одной пары он избыточен.

Referencing norms: f-0f7a887152ed2c7d767d6717, f-13709d63fadbccf1566fe233, f-1513be4c1baf72ff58eef935, f-187d9dd82610609189210c8f, f-1ba67056643b9f074b0c09be, f-1ed455f1aeffffe3ab6b1c5d, f-20cbc62f390620dfa5eb70f4, f-270483ad379e0f9f0ad6b1fe, f-27c676f7afbfd140166edb62, f-27f957646d5c27e1eddb8b87, f-2bf6494d7ac4fcda6486ae9c, f-2ed97c3c23ae31d418f8252a, f-34f1c5243acdbf3d0401398b, f-357257f44da65f278599c4b6, f-3577e71fd5c078a3b9c18a4f, f-36cf6c29d71cdb0a03106322, f-376296416122c6ee236318ee, f-38e2bcc9dc8d7165c009a5de, f-3ad8612003b41255b04997f4, f-3bd86e6acb9da2cebf235c89, f-3c39f6eb773a34b2f58c3290, f-3ce4619034b3f1bcf0d857c1, f-44595c1f24be307bc4dbbed5, f-465ae260fbd3f63eecb707a4, f-485ba1f77d2ad896e5f5198c, f-51507168a74f27f61e2becd0, f-53d989935076e38644ac0e33, f-547d8d94feac97405458eb85, f-551dcbbc86506282830fa901, f-5cddd2b82ca1d2ddab878528, f-626619ea2c0a3a1d42491e21, f-6a3673bbcf53132391c308ed, f-6bd2904a7dbe9e365e8e3485, f-6fb2c3e28bf13945702babbd, f-715d288769f0a5090fcd87b6, f-735a08a5316461514c172413, f-75bb0ab8a8cb6e64e0578a69, f-76b382c0554d98d51de3b887, f-77b6438e59736a4e90180be7, f-7827c88adac494daffe84a57, f-7953d18d2bf1645bb55c9aea, f-7b89a63cdf68941434d536a6, f-8164d454fdef447b0470984d, f-8467e418d485938e93b546c9, f-8a829bad0756f9f4a5fe1724, f-8ce84df7261968619b95f2be, f-8edc3710a55f1b27c8413ba7, f-93d016de1e4fac111325f9b4, f-96da413c6bf4657481ff3af3, f-9877369b8f29ab2d03353b5a, f-98bf3a99a10bbec2470e6e95, f-9a2484e44b5e336f45f2a007, f-9b086df3ae359af3c67f0b89, f-9df7902ea7a77a46272a7142, f-a26c2d7871cfa382f9aba876, f-aa448d266815c7b5bc2c05d7, f-ad1a783132144c4817d9b8d1, f-ad3e5311f96d1f9efe9fb966, f-aec91c0cec88d80627d5096f, f-b2faeae0408d501359a639fd, f-b50baed0aa0dc757960684ba, f-b88b0f144b78870fe4c9d9b4, f-b9827b358fc5120695672179, f-bf1ff4ae272a95ad37d10356, f-c3319da67c336b394b6de8bc, f-c6ae59884dc90f150976f0e5, f-c6b6f8292624dcb272bdb7b2, f-c8765925aa2793a6c0af1da6, f-cde5ccd2a60a76f2efe14616, f-d04b63a9f9710ffbf2127fff, f-d0961d10d5ac56ea1c1e1561, f-d16a961da781613aaaff6276, f-d22d23b33c0de9653c55bdea, f-d2464a67a01e97540031e39d, f-d4d216d4e53d0dc1f803676d, f-d9da5149faa251ee02cb85d9, f-dbadcaebf327b9ba4a4d038b, f-dde0469c45254f649872d754, f-e449ba30b7b14ea4b0913044, f-e849c73d91ef24357704f6e0, f-e8a77cf942d203a6413db83a, f-ea4b6a7086528b1948049ae1, f-eb436a4ddfc11428bd4524db, f-f0f8108c46a2c1de326f0322, f-fe2fc087b8f1e97b7b2fc5b3, f-fe6d073d29d9605a9756c7a5

ru · official · sha256:fbb2f500a9bea461fc70b5d2e02fbb561cd520316377df990a47b5ca72a853f8RU

§5. Поиск A* Задача: по сети с неотрицательными весами, начальной и целевой вершинами и эвристической оценкой оставшегося расстояния найти кратчайший путь до цели. Вариант — Дейкстра с приоритетом по сумме накопленной оценки и эвристики. Отличие от §2 одно: приоритетом служит не оценка расстояния, а её сумма с эвристической оценкой оставшегося пути до цели. Поиск прекращается при извлечении целевой вершины. Эвристика допустима, когда она никогда не переоценивает истинное оставшееся расстояние. Допустимость есть УСЛОВИЕ ОПТИМАЛЬНОСТИ: при недопустимой эвристике описание находит путь, но не обязательно кратчайший. Эвристика согласованна, когда для всякого ребра из u в v выполнено h(u) не больше суммы веса ребра и h(v). Согласованность сильнее допустимости и позволяет обрабатывать каждую вершину однократно, как в §2; при допустимой, но несогласованной эвристике вершину приходится переоткрывать, и это другой вариант. Нулевая эвристика обращает описание в алгоритм Дейкстры — это полезная проверка понимания и одновременно граница варианта: выигрыш даёт только содержательная эвристика. Оценка: та же, что у Дейкстры, в худшем случае; выигрыш на практике зависит от качества эвристики и никакой оценкой не гарантирован.

Referencing norms: f-02de31f8b55aeaf1ca5190b3, f-0303611ac9641c9f6bb82a8c, f-05b1dda5c9d3bf4c2e77bd02, f-097ffd23bee9d6704e3778ed, f-0bb1a7487c9e482d407a820e, f-0f116a31288808a306cd59a1, f-19d054df81c65e65ffe0a89c, f-1d47dfc505d95518d14c1c79, f-1e35a5a6c960dad103efd6bc, f-2304448b47b4309baadbe2cb, f-25b9689a42443581a960874d, f-27148f68916d42bf6588e733, f-2839d88a7a32e4912533c4ac, f-28c9f126f7ad0cd031eb8437, f-2eac40fa54c65d97e28e7306, f-3193ce3bce230d55808613ff, f-33ccc3f6ffd0fa02a48fd965, f-348f0e4df2757da01fb01065, f-35d4310186f7456b9875034f, f-3a662bd88e4a573a8eb3ff68, f-3e927a4710b550309462833a, f-4081cc619a7309e13ea7f51a, f-40b1df0aaaab586fb31621e1, f-44158d2f14ba8e18597c1a4a, f-4807ab7ca1decbbb886c5172, f-4bd5e746ef1772fe2f411e8c, f-544e57efb778b2c9331ef88f, f-5644a8476c5ff8f9ecde785e, f-57852270646584b507d44011, f-59ee24d80270c475ba500764, f-5c7ba071e71ca2b36560c2de, f-5c91eab0b48df6afc3ef3fa9, f-5ca7b486e74b070c401d31ae, f-5ebe5db1f187c1c2b56d4fe2, f-6364d7fc25f8dbd769514ada, f-64dfb2f5df14a91d364b3018, f-650186e7a437b44959495ad4, f-66cfc8b4472aa086d049b903, f-66df83f9e384985199a1fb01, f-671732884dd1d57562c04b88, f-6a9d74442c42c4e256e2fd86, f-6afa0d72f89c10659e7c8cb0, f-6b17383c36955d6dff6b4109, f-6bb2220694a3107be01b753c, f-7016cbbd90488a27fe83ba17, f-71fe11e7c50ff4ed465a4404, f-7736d3de465547ed686d9b89, f-78a96b7b9729ae7df2e790bf, f-78eefe180e79413af83c7d43, f-7ba5c4270252b4136be776ab, f-7cbf0b2114dafd282d463174, f-7dbd56e9798b27281256941c, f-80d5206943a4bfa1c2bf4af1, f-8604e07bb3a3d85aeaf33930, f-8bf597f2d670cbdda3c889a4, f-8ca581a420ef1dff54bc74b3, f-8e3a43d46382690621030dd8, f-8ecb0d4943373874e713890e, f-91fc9f455fb06752e680125e, f-948fad84b966b01195268364, f-977a6c9e3375f983f0e72bbd, f-97b871bf19a994cc84ecfe4f, f-98e01a86605f196632b4f6e6, f-9d2095fff6943fc43e4a83e8, f-9fe09a279a70a151567be5aa, f-a28f2ee6343660ffc14ae18e, f-a7e49773804d794d5d891621, f-a8eed36ef2063c659851baca, f-af412a4017f276c1cb1a5e4d, f-b38bef181b5d7cfed5d97f78, f-b98f2d0fd09d7cec3a57a3fc, f-bba517aa62c624748caca890, f-bc317c5793f2d89e7c2ff4c7, f-bd3f8f8e50c2f39253988d64, f-bde35d6ff2930827b657bcf6, f-be8072a421ffd5d18d1b2e7c, f-bfc3cbbe38f8d10834b888b8, f-c8f51e45c7bf3bd2d0a74fb3, f-c9b9bbea1d2fde448c210f72, f-cb88365cf960ee5d7b492fcd, f-cd6e4a9d6eb07c4fd2965bdf, f-cd88b7f37af6e11f3e66f185, f-cf6425c4240ef406e81733b1, f-d54e0e9f27fd4c986a473ecb, f-d614805564932178e32ac731, f-d929ce9e4fa2da27abc1a011, f-dbceccee59437abc5515efa9, f-dc06e2e1138272d327cd13cd, f-de6d46891c02f70b0dadf713, f-dec66639c8f7e51b042ed65b, f-e3201933ecb02023847b3447, f-e40addee3251518ef3aaa4f7, f-e65db19343baefef4f1783bf, f-e7be54c2628793abe6ee8b16, f-e85d891ba08d6a5197b570f7, f-f4500474ce66462b542186e3, f-f60e10542cb5e9257ce1688d, f-f6131e1a640d9fb1d22f3bd7, f-f67730ddae20acb92957d0e7, f-f9c052c8aa2b5983ba89a981, f-fac3dc919e0b4bbfc4bf989f, f-fc4167e3236354d38f4c4122, f-fe6b693c028d9effce334966

ru · official · sha256:b87a82a4fee6f881c4bcb6cd1398ec5a8b8177639966cc628f33dfe699d16305RU

§6. Минимальное остовное дерево методом Прима Задача: по связному неориентированному взвешенному графу получить остовное дерево наименьшего суммарного веса. Вариант — наращивание одного дерева от произвольной вершины с приоритетной очередью рёбер. Дерево начинается с одной вершины. Пока в дереве не все вершины, выбирается ребро наименьшего веса среди пересекающих разрез между деревом и остальными вершинами, и оно вместе со своим концом добавляется в дерево. Основание — правило разреза §1. Разрезом служит пара «вершины дерева, остальные вершины», и выбираемое ребро есть наименьшее среди пересекающих его. Инвариант: построенное множество рёбер есть подмножество некоторого минимального остовного дерева. Это утверждение и есть содержание правила разреза; оно сохраняется при каждом добавлении. Оценка: при двоичной куче время порядка числа рёбер, умноженного на логарифм числа вершин. На плотных графах вариант выгоднее метода Краскала, потому что не требует сортировки всех рёбер. Крайние случаи: несвязный граф — остовного дерева не существует, и описание обязано это сообщить, а не выдать лес молча; равные веса — минимальных деревьев несколько, и описание даёт одно из них.

Referencing norms: f-091a978ec1a780bacd0ff86d, f-0a18eda400827c2a6a25b31e, f-0e38c4b62107c1b5218c1a3f, f-0ea4fc03fa6aa5d4251413cd, f-0f85a8b2b35b2284a8f71458, f-12646c88a7f5bdcabe04730d, f-1446624c83ded6bcd14c08ad, f-14834ec4668794a3c1c8dfaf, f-15a0f41d25337f150f387890, f-15c264edfd4ec381716bc14d, f-176193e48ad133b8c6848b73, f-18447b4ddde3bf0a470f1230, f-18a897390cacb247f0cfed55, f-1a1d9c824999a76bb4480faa, f-1cff1b305b1ba4a7b4e15289, f-2963147758a28dfe24c6f272, f-3064ea6a17b38c4daed30cfd, f-307eab5a32a4c303825e9a6e, f-31f2c988d6ebd740cd4eadd4, f-3673d8c3c12d779fdf34ffb8, f-3d4f5c6e8e5619abf46dc7f3, f-400fb0f5e22786cd67048616, f-407d541cee614f3c4f3da571, f-42c36d951495be9693aa08b9, f-45a0516114ad13f4ee674b49, f-469cf17fbdadaa9a34e40775, f-4a78d553120433d23e3c81e0, f-4ac2b4b56156604c511207e7, f-510341a6bb87bdc45f13f723, f-5690e37da084a1e5bc58390d, f-57e5de58f8247b99e165dc3b, f-581d2cfacfe80ef6885d647b, f-58fb26e96cc94aa215c3a924, f-5b6069695ba262e4ee573010, f-5c0707b3f5f78520ea8a2f10, f-657c498e22b646941b35afd1, f-66d6fc9c298135be2353e5bb, f-6a499f5376db5c0e7ba36dd0, f-6fd97aadb7564bc1e97ab133, f-73bf671e75260ffa54abea11, f-741522c44a87f9f7320ff2d7, f-77ef5681b244add60e7cafaf, f-7b68e4a80d75c18bc2413dea, f-7b945ac795554a58dce33413, f-7efcf1f1b28a98e6f9c412ed, f-89e9f4b124e603fb9036c6e2, f-8a7fdf463d4c9b7f308f57a9, f-8ae3913db06a844eb5c16859, f-8b97b8bc6fabfb67a38310fe, f-8bdea6350b659859dc0baaee, f-8f02df06af63af1c68fc9edb, f-904fb2b76435c50ed856fbb7, f-980dd981967a5315efc1af59, f-99fc39961f544495a929f1a1, f-9b747d93b0c692561802d4a8, f-9dc80c6ee3b1503999c615f2, f-a67a7ca02e83f528fd3a1680, f-a84b2f85d51bc83d62e2b7b6, f-aa6d480832800d86f0308b8b, f-aaf7b5352ed373c21bb74e99, f-b1debed3267bb80d2e2478dc, f-b67807d91d9d43dfb1fd0ed8, f-b868dbc2401cb8ec4b0fa130, f-b883ce11a9930a1e7d83858e, f-be6647c99264b6bbd3f8b21f, f-c552caf1d56af6891c4a234b, f-c7e6cd86454e7a621a492b90, f-d4e6f398c5a7f1852673d12c, f-d6248fed7868bfd7af2cc4a0, f-d9e84ccf700559fd643f2266, f-dddba90924d6808e3f8d560d, f-df99550081aa0c75aede68ab, f-e061fdb11c42bcedc132ab5f, f-e23cdfe527e88ce062fdf1e2, f-e5c77dfcfa9a2b57ca2d8f2a, f-e9e03d3b9f905224a9bf1db3, f-eae2ed1843a994d9fd71de3c, f-eb29ffb028069636febcc41b, f-eb7e1ce88dc6710cb4492cd1, f-f1956b32a2232d3dbdefef8a, f-f21a4235789b560f10040817, f-f4bbc978c57efd29f3f9fb47, f-f65949330c183734d73796a7, f-f83c27f2d30ae78ebdb9f483, f-f8615ca77615e2ee5dad3395, f-f8c72af115266462bbedb109, f-fb5c0e8daaa32b417b4cc68e, f-ff238013b43dd9f552f268ba

ru · official · sha256:36357e6faba25956b2b8a7fd5a669836d1ac82ff483376f7a38cd711b9b03f16RU

§7. Минимальное остовное дерево методом Краскала Задача та же. Вариант — сортировка всех рёбер по весу и последовательное добавление тех, что не образуют цикла, с проверкой через систему непересекающихся множеств. Рёбра сортируются по неубыванию веса. Каждое ребро проверяется: если его концы лежат в разных компонентах уже построенного леса, ребро добавляется, и компоненты объединяются; иначе ребро пропускается. Основание — то же правило разреза §1, применённое к разрезу, отделяющему компоненту одного конца ребра от остальных вершин. Добавляемое ребро есть наименьшее среди пересекающих этот разрез, потому что все меньшие уже рассмотрены и либо добавлены, либо соединяли вершины одной компоненты. Система непересекающихся множеств со сжатием путей и объединением по рангу даёт почти постоянную стоимость проверки; точная оценка выражается обратной функцией Аккермана и принадлежит источнику. Инвариант: построенное множество рёбер есть лес, являющийся подмножеством некоторого минимального остовного дерева. Оценка: сортировка рёбер порядка E·log E определяет стоимость; на разреженных графах вариант выгоднее метода Прима. При заранее отсортированных рёбрах стоимость падает до почти линейной. Крайние случаи те же, что у §6, плюс один свой: если по исчерпании рёбер добавлено меньше V − 1 рёбер, граф несвязен.

Referencing norms: f-0363a944bcaf4198270cbbdf, f-0d5ca2b3009aac8dc6a3d6dd, f-117302256ac35e29f611b4aa, f-17303295ccd16144d4954357, f-187f60fd5d305e28f95a1cb6, f-239e071fa38923e952a4204c, f-26287b116b280704a92c2c31, f-275a9fb0e6bc405c9638949b, f-289fd4f718ac8ff4f7ec4555, f-29e845a77506340ea63ed845, f-2ad716b29ddb43654f9246d9, f-2baafbbb36bbde651288f69d, f-30cb2fada3af4f2262d66243, f-330a250af5a87ab322617ef8, f-35101efac87f5088bf1744e6, f-351e4f5e57b87748b87a0a5f, f-35d2f81f45dfc4031df7b051, f-367d4fb161aa04486bdec9ec, f-38da4e810e069067eefdee04, f-3aa9522031bcfb18a3595733, f-3c3ae36849426172bdcf7119, f-3caf4e4beba933b7d310e4d8, f-413cc16bd4dd58e4931e4be6, f-4410d4c3f6de39e98cbe3971, f-44d4afc7754ba50c4f71599b, f-479ba2e15f6b133b745d7563, f-552142ed80e8e04ebf1f63ae, f-5622b031718b6c06d1615ddc, f-57ff69125d6bf7b4f70d8109, f-5a651ca70e22fc266d2e3b05, f-5a73d04481b364d91353b29c, f-5b74b21abbb31df5e252f5e3, f-5e71c3202d782d22157dbbc6, f-604bf6ce82ffe10a0f4c38f3, f-64e4d2cb5a82b7a433a5f3a7, f-666b4661ddfdaa793f33adae, f-6b5ce19167e94f535341877b, f-6d7649e4e92732eebeb629b7, f-70cc5df4a97de7e0fbde44b2, f-71da84268e7acc90a3f0d012, f-7571b9db7d6f6ff8302beef2, f-757cc817f8d4fa09783daf43, f-7642598926d87215fe589909, f-792a93cb543ea62e0c0d7a82, f-798cbdb9d51ee9351f59ff4c, f-8195337d6a9423e64637f7e3, f-8aa0fca61444b05a7979aa27, f-8cd398a8887485ee6cc9c858, f-8f249dfde8fd6c510b5e0736, f-9121db14c01411cd02f10794, f-925421ef11e18e7a0391ea12, f-9475155a76d3bf22db950cd2, f-9654331460fc01d6de51086c, f-97b59462b0e0ee2ed2d47046, f-9f2a792d06253506611ed17e, f-9f546414922e95ab51b1a4c9, f-9fa5fac8307088013e349f10, f-a19024ecbbf4c1b65ea899d9, f-a2110911cef16a6594d8bc26, f-ac9c9f4b6d64bd82f35b9335, f-b04663459468d734747b964c, f-b3676c23c83c7d26d2be152e, f-b4038f19c8cf5a26a910dfee, f-b40ed1e234edb8e96f7bb8c2, f-b55982131b7a1f412677f9e3, f-b5cc71061f3ec5a2a02728b7, f-b60f87b4a2b0be9fbbd8fd4b, f-b70e08fd6faf92dcfa461760, f-b83036b4903430d98b9fc967, f-b8b29a4a60b8e99e02b72e59, f-bb4b19ca4ae4abe1be9660f9, f-bddcca72bdf7d1e4d27829bf, f-c00e6dc4c264fcf941705fd1, f-ca61ec5efecef1bede6d2efd, f-ce0b6c9a7ebf9bab2c571ef6, f-ce33cc595bb928190b1441c9, f-d254cae10ae879df71e7b617, f-d2a884d468f1fde23ebbc94c, f-d335c6a2532ad198df2eab20, f-da71b7f09fe8cf21ef776b6c, f-e0dbe361f970525469957c14, f-e63ad59f13d3b1b9c4d27b84, f-e9c7a9014373c91eb13b7683, f-ec51d7a7c94464d9b227db89, f-efab04a82f8d20b3a4c631e4, f-f00ff9ff75f7dc3c39a4075c, f-f40ecfc5ab4b850edc4bef4b, f-f41e0ed0a39c3649b100c34c, f-f57f03a78d87d5b99d992f2d, f-fead0e8a3fcd96be069881b1, f-fef7860775da88a3dae9759a, f-ff48cbe73ba4ab83160db46a

ru · official · sha256:4182e8c06c48d549da54c6e0c80426fee7bc72728fc29db3fd82ba41598eced1RU

§8. Максимальный поток методом Эдмондса — Карпа Задача: по сети с истоком и стоком получить поток наибольшей величины. Вариант — метод дополняющих путей с выбором КРАТЧАЙШЕГО по числу рёбер пути обходом в ширину. Поток начинается с нулевого. Пока в остаточной сети существует путь из истока в сток, находится кратчайший такой путь обходом в ширину, по нему пускается поток величиной, равной наименьшей остаточной пропускной способности пути, и остаточная сеть обновляется: прямые рёбра пути уменьшаются, обратные увеличиваются. Выбор именно кратчайшего пути — не удобство, а причина завершения с полиномиальной оценкой. Метод Форда — Фалкерсона с произвольным выбором пути на иррациональных пропускных способностях может не завершиться вовсе; это утверждение источника, и оно объясняет, зачем нужен обход в ширину. Основание корректности — теорема о максимальном потоке и минимальном разрезе §1: отсутствие дополняющего пути равносильно максимальности потока. Оценка: число дополнений не превосходит произведения числа вершин на число рёбер, делённого на два, а каждое дополнение стоит один обход в ширину; итого порядка числа вершин, умноженного на квадрат числа рёбер. Оценка не зависит от величин пропускных способностей — это и отличает вариант от Форда — Фалкерсона.

Referencing norms: f-006c92f969fb011e1bf87956, f-02502bd41dc2ba8ca6712baa, f-085848eb8085e84df6e8d89f, f-095988b03d1b619b230fce17, f-095e7b8c846519e9008fd35b, f-09f5761a8414510e9564da93, f-0e015e3c68ae7b19e30165ee, f-102546f17d3df7fad851194d, f-14f808f2780368d9c04a08fd, f-15a8bb49dd95bbc3ed02d52d, f-182cb4d9b07c3a122008306f, f-1dbf6143e802c08f0d66be84, f-2a10beb75baeb30b0d4cfc60, f-2a4112c125e0e2fe0cb01964, f-2d497f18c7b08dab52c7844d, f-3734819f4a365bbd3ee731d4, f-3933d29f3969fcc740cfb9b3, f-3dd88d755eabfa21c3c12a5e, f-4941463483a187b18bc0af4e, f-4a1798a5278233cf6bd16efe, f-4a5283f8d6eb499f0860331c, f-535cd47a9161ff15010fb3a5, f-53fc59f4c6b21f76f2de2cf1, f-5b64a81fa5664081b6ce5c4b, f-612c35c9cec67436829b16d5, f-6197f2c6d2ffe321dc44bcd4, f-620d32723112dcd99263fc6c, f-633086941edf17503ad53730, f-64f141ee158377af3a021bd6, f-6a2d02784fb4a37bb80f4329, f-6f4dd7e4f0f6854e787aee38, f-7124c474702632e6da98fb5d, f-737506a96ea1498b70f6fee8, f-76bbb4d05049a17e13d91010, f-7b20a963cfd19be0e20999db, f-7c607428706be0c279acb260, f-7c7d6f31dce12f4d05a793a9, f-821b41c52adffd009c94a2c5, f-823b28823297df2a7df65266, f-82e274af335fec1ecaa14e29, f-831973300cdb3757e4e3a8ab, f-84b2f582696fb2b7408fd7e9, f-8a47008ee88236c852b9ed92, f-8f3eb472f82342453597106f, f-91f367e4533882430fe5bcc4, f-9319d3fefd7564ae937336e5, f-97ef230311bb36eea02cdd83, f-9dbdccfee6751bc829124c80, f-a1189f45c453c5a3415e3b6b, f-a3850b20488bc5bfca4828a2, f-a448fa320d33f9e788e44f14, f-a79623d0621cb23753a2a1d1, f-ab8fda71d8ad5a8c173dbc64, f-acd0a764fe43e888eddb9baf, f-b28a2a10615a6218eaffa780, f-b4a0ffefe266409ba839d0cc, f-b5e41e03b479d71330ca02ec, f-b6496fd2118cfd6f67e2d29f, f-b6e06aff52b351e5fad265ca, f-b824ccf6e848e3c79ed18149, f-b8c9a9b247461b7d2e74aec3, f-ba6c2f2f9830c5fee8935f99, f-bb667429d5b36bf683bb1e05, f-bc8ffe3ae41af85534bf5477, f-be5b7fa593cafdc663637abf, f-c25e64fdc03348479b2898d1, f-c80cf3e678401ec7967911ca, f-cc994ec17faea8abab0344bf, f-cd2e7811f34066802f480aa9, f-cfc1c425406f76b756427315, f-d0f37b7b9ce99eef89196317, f-d1b89f9596fb91423a4562a0, f-d36807e938cdbe30349937b2, f-d3a2908035a8f7d8e1b586df, f-d72b6712702d95de220c174a, f-e72fcaf7a39ca9ee51018f67, f-e73a12db4467e215f9ee3e07, f-e7757651fbd4226291bfadd1, f-e838501ef5b54f0e581e67ac, f-ea984ec6f1de053c692e2e5c, f-ecbe9bd53004cef801888a2d, f-f66f9936416fea9f7de04f9f, f-f67dc82b80e414034531ff3d, f-fcdb06a1633e37deba2a1660, f-fe31457545e5d08877129e8c, f-febd98ef98518ce9f0110a99, f-ff066d0c942e9131bedd8467

ru · official · sha256:cddcfd5021c7a8dcaee52cdc3fe242b216987c13ff12f64ae54aabb3dd569479RU

§9. Максимальный поток алгоритмом Диница Задача та же. Вариант — послойная сеть, построенная обходом в ширину, и блокирующий поток в ней, найденный обходом в глубину. Повторяется следующее: обходом в ширину строится послойная сеть, в которой оставлены только рёбра, ведущие из слоя k в слой k + 1; затем в ней находится блокирующий поток — такой, что всякий путь из истока в сток содержит насыщенное ребро. Найденный поток прибавляется к текущему, и построение повторяется. Расстояние от истока до стока в остаточной сети строго возрастает после каждой фазы. Это утверждение и есть причина, по которой фаз не более V − 1; его доказательство остаётся в источнике. Поиск блокирующего потока ведётся обходом в глубину с указателем текущего ребра у каждой вершины: ребро, оказавшееся бесполезным, больше не просматривается. Без этого указателя оценка фазы теряется, и вариант вырождается. Оценка: не более V фаз, каждая стоит порядка произведения числа вершин на число рёбер; итого порядка квадрата числа вершин, умноженного на число рёбер. На единичных пропускных способностях оценка улучшается до корня из числа рёбер, умноженного на число рёбер, — утверждение источника. Против §8 вариант выигрывает оценку и проигрывает в простоте: у него две вложенные структуры — послойная сеть и блокирующий поток, — и обе обязаны быть названы отдельно.

Referencing norms: f-002334309abc9359bb574802, f-00d87d638d36fc44dacbed8b, f-02a2e68d492acbc1420bafe5, f-047e46ef902b292252f6692a, f-096ce6cd53ff6f460cfb1d14, f-09eb20957442b1c6570b3a56, f-0d07ab8d4438f1f6be5c288d, f-0e5152ee651bd631f94e922b, f-13482cd2c7644db403cf7dc1, f-17910fcc6ea16490f4d319e4, f-1b4c98677777417ca47209a0, f-1bf67dd7f234f6420a888bbb, f-1c0a47ef67b8010986caec28, f-1e5ce77c68d2c2de861b65ff, f-20a14301e89cdeea9e7eb70b, f-21943208df8b8b48835f76a3, f-22c404e8e2580b5c13a1695a, f-33481eda8bab7d7a0043ccad, f-3447651d772de320d12c08aa, f-35f6286fa7984641228733b8, f-36353ddfdd5c9beb92740393, f-3bce18e203c6d5ce40691451, f-3f425f8b82a9397f1bab03d4, f-41ffa314cadc5525ecec5d6d, f-45f8ff3dc264b5eb5f95dc97, f-48917422a28f37e666226382, f-4a3d8e4b7e1fd27edcc9dc3c, f-5b4bf1459c18d97d9c6c2e95, f-5d8b0ca9565fc75cceae22f1, f-5edb84d8a030890799aa9977, f-60e914ce5d0d2e3f90e72558, f-669f8ca1c71f77d12aab12c4, f-68b412eb77b20a668151533d, f-6a59844da963b5762c3477de, f-6a88adda8d702277a9432883, f-6d2842dedfc3f2206b65255f, f-73ed10cb3067a792732e02dd, f-75ba7c740f385ec8c99db573, f-7a0a4c8ad3195da15dc31769, f-7fe24daf5b50a0078013a07f, f-853074b283c123bd7f952034, f-853c79bc98df32321072dfdc, f-86981e0332425862966e0b5f, f-88c17a04f4d58b65947473d9, f-8a0a651b75593ae8b670b559, f-8d79f612ee178dead0f8e8b8, f-8fc9411141d110c3560133b7, f-9332091be874240ac7d20aa0, f-939fd43c1f14c776d4e6c4c4, f-96bcd81b35a9b5c9cd288ac5, f-9b64d5d15ec254afb3c00a99, f-9b755034375da9b1e539111c, f-9c12472ed400da7e1a8c3dbd, f-9e8ca8a6d27c0935c80db5b0, f-a0f876170f18ca7b2bd2df4c, f-a5f053b6b56d1914e88bdba5, f-a68902c5f21967aff22620b4, f-a75288c36d1a52756747f3a5, f-af09e731fbd08dce279f64d6, f-af0cbca80316aa1893134047, f-b0a703a78138050f22d63cfd, f-b6e0bd1f441231c9c410908e, f-ba1cfeacf563fe060df67c18, f-bb2011a1ce3d60a415d068de, f-bb5896bde62b44b26ac15860, f-bd2db89ffacea8e821214e6c, f-c14d82086e797d0891d33b47, f-c66c3f80416ca59427451292, f-c67206edde9fa77685bd8972, f-ca5bef62fb18dd669a44a729, f-cb26a908b51c418f28a2648c, f-cd572dccf5dfc3e977106cfc, f-d1d0585358406c405d24c617, f-d94d58a34729c81e94bf1f33, f-dbe6c7099ac92ccbfc3a66c9, f-dca6dff1b595a9f54d5e8565, f-df5e1edb2c4b47d37af291c6, f-e3a36b7eca1869a0843385db, f-e59cbf8a449344e19aaf544b, f-e5be56226128480a5a5bbd7e, f-eaf4bfefda3df86f143da459, f-f2c198bf90ffaf0461841f21, f-f54582b5397be5448cc9f1c5, f-f674e6a24352f5c395cd4505, f-f7567f1ca8ee6b4af345ffa6, f-f7837df146a004dd4ef61a13, f-f91ba1ed33a7a8fd66dd3044, f-f997a96947d2b27e7df3464d, f-fc111c82dcebb59d4caabc95

ru · official · sha256:72f73bde542ed8786e024b0cf790f46fcd24e8b2463646babac349b379de4262RU

ПУТИ И СЕТИ: ДЕЙКСТРА, БЕЛЛМАН — ФОРД, ФЛОЙД — УОРШЕЛЛ, A*, ОСТОВНЫЕ ДЕРЕВЬЯ И ПОТОКИ Настоящий документ является АВТОРСКИМ ИЗЛОЖЕНИЕМ, составленным для целей формализации. Он описывает устройство восьми алгоритмов: четырёх поисков кратчайших путей, двух построений минимального остовного дерева и двух вычислений максимального потока. Изложение не воспроизводит ни один учебник; происхождение каждого алгоритма названо при его описании локатором. Описание отвечает на вопрос об устройстве алгоритма и не выполняет его: ни один граф здесь не обрабатывается.