только если вы не торгуете оружием, наркотой или не занимаетесь терроризмом
А как же пропаганда одобрения и одобрение пропаганды экстремизма? А дискридетация армии? А распространение информации об обходе блокировок? Более того, там кого-то уже судили за публичные действия, потому прослушивающего личный разговор мента судья признал за публику. Так что если кто-то ваш host почитает и там, не дай бог, ересь какая-нибудь присутствует, вас уже могут посадить. Ведь нет оснаваний не доверять сотруднику, да и эксперт все что надо подтвердит. Плюс, список расширяется с умопомрачительной скоростью и рано или поздно даже попытки обхода блокировок будут караться.
Так что если вы еще не сидите, это не ваша заслуга - это их недоработка.
Случайно натренировали сетку определять красивые/симпатичные лица? Не секрет, что привлекательные люди живут на легком уровне сложности. Им много чего прощается, к ним более благосклонны окружающие, им дают больше шансов. В среднем такие люди более успешны чем некрасивые с такими же личностными качествами, навыками и знаниями.
Спасибо, стало понятнее.Разделение дерева какими-то свойствами обладает? Например, в отсоединенном куске будут только элементы с меньшим приоритетом?
На одном уровне все элементы с заданным приоритетом?
Искать родителя\ребенка от ребенка\родителя, бонусом по индексу в уровне;
Что значит родитель в этой парадигме? И зачем вам его брать? Дерево - это внутреннее устройство структуры. Вообще говоря, снаружи вы о том что там вообще дерево можете и не знать. В insert() у вас никакого понятия о родителях/детях нет.
Дерево не ориентировано на частые изменения приоритета \ добавление новых элементов;
В таком случае вам не нужно дерево. Вам достаточно std::unordered_map<int, vector<Data>> priority_to_data. И еще в нагрузку к этому vector<> всех приоритетов, которые в структуре есть, чтобы можно было быстро брать следующий, предыдущий приоритет.
С разделением на части только не понятно немного. Возможно каждый кусок будет иметь свой вектор приоритетов и шарить один unordered_map. Если надо совсем быстро, то vector приоритетов тоже будет общим, и каждый кусок будет хранть array_view какой-нибудь на него.
Если я верно понял, вы имеете ввиду описание реализации дерева.
Нет, я имею ввиду описание того, что дерево делает. Какую задачу структура данных решает вообще. Я вам даже кучу примеров описания для других структур привел.
Приоритет самый простой, как например в бинарном дереве,
В бинарном дереве нет приоритетов. Приоритет есть в куче.
Я хотел рассказать вам о идее(концепции) такой структуры и поделиться своим проектом,
Ну вот никому ничего не понятно, потому что неясно, что это вообще за структура и что она делает, зачем она нужна. Вы какие-то детали рассказали, но вообще не те, которые нужны для этого рассказа.
Остается только доказать правильность этого метода, и это несложно — подумайте сами.
Как обычно бывает со многими "это очевидно" - автор не смог сам доказать.
Такое объяснение может дать интуицию того, что именно алгоритм делает. Может даже помогает его запомнить. Но без теорем, лемм, математической индукции и всей этой "скучной" мишуры вы не докажете, что алгоритм работает.
Почему вот тут, если одна девочка попробовала все "ребра", не нашла себе пару, к ней не надо больше никогда возвращатся? Ведь подобавляв других девочек мы что-то поменяем в рассадке, почему не может вдруг оказаться так, что вот та девочка без пары теперь сможет найти себе пару? Если это не так, то алгоритм был бы за O(N^2M), ведь после каждой перерассадки надо было бы опять проходится по всем девочкам без пары и запускать поиск.
Почему вы в dfs не зачищаете пометки после поиска от каждого ребра? Вот попросила девочка 3 мальчика 1 с ней сесть, он спросил девочку 1, та спросила мальчика 2, потом что-то и еще и не нашлось ничего. Почему вот тут девочка 1 даже не будет справшить мальчика 2 с ней сесть? Ведь теперь мальчик 1 не пытается с ней сесть, девочка 3 никуда от него не ушла, почему не надо запускать всю цепную реакцию опять?
Почему алгоритм вообще находит максимальное паросочетание? Почему обязательно найдется такая цепочка из девочек-мальчиков, увеличивающая количество пар, если паросочетание не максимально?
Еще, этот алгоритм - это алгоритм Куна, а не "венгерский". "Венгерским" называют другой алгоритм для поиска паросочетания минимальной стоимости ну или для решения задачи о назначениях.
Такой процесс называют построением максимального потока.
Вообще нет. Абсолютно нет, как вы вдруг переключились на потоки? Это называется построение удлинняющей цепочки.
Если там вся книга такая, то могу лишь посоветовать никому ни при каких обстоятельствах к ней не приближатся вообще.
В статье очень не хватает хоть какого-то описания, что же это за структура данных-то и какие операции она выполняет.
Например, приоритетная очередь позволяет добавлять в структуру элементы с неким параметором "приоритет" и неким ключом, выдавать и удалять элемент с максимальным приоритетом и иногда изменять приоритет элемента с данным ключом: Insert(priority, key), GetMax() -> key, RemoveMax(), ChangePriority(key). Бинарное дерево поиска позволяет добавлять элемент с ключом, удалять элемент по ключу и проверять, есть ли данный ключ в структуре, перебирать элементы в порядке возрастания ключа: Insert(key), remove(key), HasKey(key) -> bool, enumerate()-> key[]. Хеш-таблица далает все тоже самое, кроме перебора элементов по порядку возрастания ключа. Дерево отрезков умеет изменять значение по индексу и выдавать сумму или максимум на отрезке между заданными индексами... и так далее.
Вот также надо расписать все ваши операции, без этого вообще непонятно, зачем нужна ваша структура и нужна ли она вообще. Что за приоритет, что там меняется вообще, а что неизменно? Может, ваши операции с такой же сложностью выполняются на обычном массиве или связном списке. Может, вам подойдет обычная сортировка подсчетом вместо какой-то структуры данных, если вам надо упорядочить "клетки" по приоритету.
В первой статье иерархия исходит из строки, над которой строится граф, ведь подстроки можно организовать в некоторую иерархию по вложению. Это не какой-то тип графа. И там нет никакого определения иерархических графов.
По второй ссылке действительно есть некоторое определение, вот только оно к вашему графу не имеет никакого отношения. Там иерархия - это отдельная структура, заданная над графом - дерево, в которое организованы "фрагменты", подграфы исходного графа. При чем этому определению вполне подходят и графы с циклами, где нельзя, как вы говорите "выстроить вершины по уровням".
Третья - какой-то студент отсебятину какую-то написал.
Вы точно понимаете о чем пишете? В C# любое изменение размера массива приводит к выделению памяти для нового, копированию данных из старого и удаления старого (не сразу конечно, а как там сборщик мусора решит).
Вам выше уже написали. Понимаю. Почитайте про свойство capacity у этого list. Пока добавляемые элементы помещаются в capacity, все происходит за O(1). Если нет, то вот тогда происходит реаллокация. Но трюк в том, что выделяемый размер примерно удваиваится. В результате, если вы в массив N раз чего-то добавили у вас суммарно будет выделено максимум 2N байт памяти за log(N) аллокаций и все элементы суммарно будут скопированы максимум 2N раз. Что дает в среднем O(1).
Аналогия мне непонятна. Дейкстра берет веса всех рёбер что есть в графе, он в принципе не сможет ничего посчитать если этого не сделает, а значит если в графе N рёбер, то и будет N действий, откуда там взяться N в квадрате я вас не понимаю.
N обычно обозначают количество вершин, но ладно. Дейкстра выполняет O(V log V + E) операций. Но в графе O(V^V) путей. Не квадрат, а в степени. Если считать за N ребра, то путей получается O(sqrt(N)^sqrt(N)). Например полный граф, тут количесество путей - это все упорядоченные наборы разных чисел от 1 до V, ведь вы можете в каком угодно порядке обходить какие хотите вершины. Их O(V!). Так что дейкстра никак не может рассматривать все пути, их на много много порядков больше чем ребер. Еще раз аналогия - комбинаций в замке с N цифрами - 10^N. Но, если вы умеете по началу комбинации понимать правильная ли она, то вы можете подобрать код за 10*N операций. На много порядков быстрее, фиксирую правильные цифры слева на право. Вот и Дейкстра так же: вместо перебора всех путей, он перебирает только "начала" путей, фиксируя кратчайшие пути и продлевая их. Но это работает только если кратчайший путь в вершину V через U точно совпадает с кратчайшим путем в U в начале.
Перебирая все рёбра я переберу все пути автоматически, вы можете задать любой критерий оптимальности и получить результат
Нет. Еще раз, кодовый замок: Вы не перебираете комбинации, вы перебираете только одну цифру. Вот попробовали вы цифры 0-9 в самой первой позиции, услышали щелчек на цифре 7 - вы знаете, что код начинается с 7. Вы уже не будете перебирать 9*10^(N-1) комбинаций, начинающихся с любой другой цифры. Так же и дейкстра - он никогда не перебирает заведомо не оптимальные пути. Найдя один кратчайший путь в какую-то вершину он уже никогда не будет перебирать ни один путь, проходящий через эту вершину и не начинающийся точно так же. Именно так он среди O(V^V) путей находит лучшие всего-то за O(VlogV + V^2) операций.
Нет, такие коллизии невозможны, именно поэтому из оригинальных данных строится граф на первом этапе, он учитывает все условия и если такая коллизия могла бы появиться то алгоритм просто не создаёт их в принципе, то есть у вас всегда будет путь через Б отдельно от пути через А, они не встретятся.
У вас в одну и ту же вершину можно прийти разными способами. Это видно на картинке. И вы сами сказали, что длина следующего ребра из этой вершины зависит от всего пути, вы сами сказали.
Я так понимаю, количество бит, чтобы закодировать кусок данных, сответсвующий ребру, зависит от того, что у вас там в словаре уже раньше записано, а это определяется ребрами, по которым вы сюда пришли. И вполне может быть так, что записав ту же самую прошлую часть файла но менее оптимально, у вас можно следующий кусок закодировать гораздо компактнее. Это именно так коллизия, о которой я рассказал.
Он и будет один и тот же, если бы он имел возможность в этой вершине быть более чем одним значением, то у вас было бы две разные вершины
Но тогда длина ребра не зависит от того как вы в вершину пришли, почему вы говоли выше, что зависит? Вы же писали, что длина может быть разной:
Ну так и смысл функции в том чтобы учитывать прошлые ребра, прошли по A-B у вас путь B-C стал 10, прошли E-B у вас путь B-C стал 7. То есть важно откуда вы пришли.
Если же у вас для этих двух случаев будут разные вершины, то у вас вершины графа соответствуют различным путям в графе, и вы тут путаете два графа. В первом графе у вас вершины соответствуют, я полагаю, позициям в файле, а ребра - записи куска файла. Тут длина зависит от того, как вы в вершину пришли. И есть второй граф, где вы каждому возможному пути в первом графе ставите в соответстве вершину. Этот второй граф будет взвешанным, в нем длина ребра константна, и на нем можно запускать Дейкстру. Это именно тот граф, на котором я вам предложил запускать А*.
Ха, это решается онлайн системой для проверки заданий и уникальным одноразовым кодом для доступа к системе в каждом экземпляре. Еще можно каждый год чуть-чуть менять числа в задачах.
Проблема выпуска учебников (скорее даже методичек) только чтобы заработать - весьма распространена очень много где.
Как же они в нормальные игры играют? Шуттеры всякие и стратегии?
Есть мобильные шутеры, например call of duty, фортнайт. Есть выжывачи всякие, есть майнкрафт и куча других 3d игр от первого или третьего лица. Есь очень прилично выглядящие экшоны вроде genshin impact и прочих ААА донатных помоек.
Но не графонием одним игры богаты. Сейчас на ПК и консольках ААА игры выглядят зачастую не лучше того, что было лет 10 назад в основном. И современные смартфоны весьма мощные по тем временам. И есть очень красивые игры и на смарфтонах.
Геймплей можно и на смартфоны завезти, было бы желаение.
Управление в принципе на смартфоне работает для всех игр, в которые можно играть на геймпаде. Стратежки реального времени - да, вот в это на мобилках играть тяжко, так что их мало, но они есть. Хоть и не пользуются популярностью (а они и на "взрослых" платформах не пользуются популярностью).
Главная проблема мобилок, что там пользователей приучили донатить и все игры - донатные помойки, да казино для детей с лутбоксами и гачей.
Ну вы хотя бы дословно можете перевести слово List, но и доступно же определение, в чём спор?
Почитайте какую-нибудь книжку по структурам данных. Почитайте вашу же ссылку. Там написано: что этот List дает доступ по индексу. Ну и дальше в документации написано, что этот доступ идет за O(1). Так что это выглядит и крякает, как массив. Массив и есть. Динамический, правда, а не фиксированного размера, но от этого работа с ним не начинает тормозить. Максимум, там проверка выхода за границы массива. Вон, в С++ это называют vector. В java ArrayList.
Очевидно что массив быстрый, но дорого обходится изменение его размера
На самом деле не дорого. Ассимптотически за O(1).
С чего вы решили что задачи highload и задача с Дейкстрой
Ну я же попросил вас этот код в "задаче с дейкстрой" применить, а вы отказались, потому что у вас highload.
Путь состоит из рёбер, перебирая все рёбра вы переберёте все пути, в этом смысл Дейкстры.
Тут разница как в переборе кода на кодовом замке целиком или по цифре. Дейкстра перебирает только одно ребро в пути, находит лучшее и фиксирует его. Как если бы вы в замке по какому-нибудь щелчку могли понять, что вот вы первую цифру правильно набрали. И в итоге вам для отгадывания N цифр надо 10*N попыток а не 10^N. Всех путей в графе экспоненциально много, поэтому дейкстра, которая работает за полиномиальное время никак не может их перебирать.
Поэтому надо разделять, что вы там перебираете - все пути, или все ребра, продолжающие оптимальный путь в данной вершине.
Ну для вас смысла нет, а для меня есть, зачем мне перебирать 2 млн рёбер если я могу перебрать 1?
Скажите, как вы остекаете ребро даже не смотря на него? У вас какая-то особая структура графа, что вы в момент его построения можете заранее понять как не строить какие-то ребра? Причем сразу пачками? Если же у вас в коде есть хоть одна строчка, которая определяет, надо ли вот это ребро выкинуть, то вот вы уже на это ребро посмотрели. А сделали ли вы это один раз при отсечении ребра, или один раз внутри дейкстры - не особо большая разница.
Потом, у вас не столько отсечение ребер, сколько вы выбрасываете из рассмотрения какие-то вершины? Это значит, что у вас не задача найти пути до всех вершин, которую и решает лучше всего дейкстра, а задача найти путь до одной конкретной.
нет, это только добавляет условие. Принципы работы какие были такие и остались.
Вы понимаете, почему Дейкстра не работает, например, с отрицательными ребрами? Что в алгоритме сломается? Это же всего-лишь дополнительне условие!
Вот с изменением длин ребер в зависимости от прошлого пути сломается вот что:
Вот вы в алгоритме дейкстры делаете "релаксацию" ребра, когда обрабатываете какую-то вершину: если путь по ребру из вершины в следующую вершину короче чем то, что у вас записано, вы этот путь запоминаете как новый кратчайший. В обычных взвешанных графах вы тут просто берете и прибавляете длину ребра к пути. В вашем случае, раз у вас длина зависит от предыдущего ребра, вам надо взять весь путь. Ну и допустим в текующую вершину есть 2 пути, один длиной 10 через вершину A, другой длины 8 из вершины B. Вы запомните путь через B, так, ведь он короче?
Допустим ребро в следующую вершину будет длиной 10, если вы пришли из B и длиной 1, если вы пришли из А. Вот вы и начитаете путь длины 18 в следующую вершину, через B, хотя есть путь длины 11, через А. Потому что алгоритм дейкстры хранит только одно кратчайшее растояние до вершины, и пытается вот этот один кратчайший путь продолжить всеми ребрами.
Выше простой метод который возвращает константу. Но что мешает мне этот метод сделать более сложным? Дейкстра вообще не в курсе, он всегда получит свой int и будет работать с ним, какая разница как именно этот int сформирован?
Дейкстре важно, что этот int будет один и тот же независимо от того, как вы в вершину пришли. Зависит только от последней вершины в пути, и вершины в которую вы путь продолжаете. За счет этого допущения он позволяет себе фиксировать для каждой вершины один кратчайший путь и забывать про все остальные. Выше я привел пример, почему в вашем случае это делать нельзя. Может быть так, что кратчайший путь в вершину U + ребро UV не обязательно кратчайший путь в V через ребро UV. А это основной принцип на котором основан алгоритм - он хранит только кратчайший путь в каждую вершину. Потому что в взвешанных графах не важно, как вы в вершину пришли: если вам нужно получить кратчайший путь через вершину, вы можете просто продолжыть самый короткий путь в нее.
Вершина обрабатывается ровно до тех пор, пока не закончатся рёбра в неё ведущие, после этого вершина выпадает из списка.
Это в нормальной дейскстре. В вашем графе может быть что угодно. Ибо, если запустить на вашем графе обычную реализацию, она найдет не оптимальный путь, а восстановление ответа вообще может зациклится.
не знаю как у вас, но у меня сначала строится граф, это отдельный процесс хотя и довольно быстрый, а уже потом с самим графом работает алгоритм, так что как искать путь не имея входящих данных я не представляю.
Граф, где вершины - это все возможные пути - он слишком большой, чтобы его в память засунуть. Но A* не надо знать весь граф целиком для работы. Ему надо лишь уметь получать ребра исходящие из заданной вершины. Их можно генерировать на лету. Берете текущий путь, продолжаете всеми возможными способами, смотрите в какой-нибудь хеш-таблице, какой номер у вершины для получившегося пути. Если его там нет, назначаете следующий свободный номер. В результате весь этот расширенный граф не хранится, а хранятся только данные относящиеся к вершинам, которые алгоритм посетил. За счет отсечения A* посещает лишь малую долю вершин.
списки и linq, это же тормозилка педальная. Я решаю задачи по highload и ни одно решение где я бы применил List<T> или LINQ
Вы запускали? Linq там используется только в hasEdge, который я попросил закоменнтировать и removeEdge, который вам не нужен. Да в выводе ответа. Это погрешности, даже если оно тормозит. А List<T> - это не список, а массив. Тормозит не сильнее vector в С++, который я всю жизнь использую даже на олимпиадах, где скорость ой как важна. Список в C# - это LinkedList.
Я решаю задачи по highload и ни одно решение где я бы применил
Highload у вас, ха! С жалкими миллионами ребер. Highload, это когда данных столько, что надо запускать на кластере, ибо они в RAM одной машины не помещаются. И при этом надо выдавать ответ в течении миллисекунд. Это точно не ваш случай.
А как вы хотите получить все расстояния не перебрав все пути? Дейкстра приходит в узел, берёт рёбра и идёт по всем, посещенные отмечает, собственно узкое место как раз в том чтобы отсеивать ребра.
Опять у вас с терминологией проблемы. Перебирать все ребра - это не перебирать пути. Перебирать пути, это пробывать a->b->c->d, a->e->d, a->f->c->d... Путей в графе экспоненциально много. Ребра вам итак все придется просмотреть хотя бы по разу, а дейкстра именно столько раз их и смотрит. Меньше уже никак. Их отсекать смысла нет.
а противопоказание в чём? Дейкстра из коробки не запрещает убирать узлы (сиречь рёбра) из списка доступных, это же его суть работы - посчитал, убрал, посчитал, убрал, что плохого в том чтобы что-то убрать еще?
Дейкстра "убирает" вершины, до которых путь уже найден. Дейкстра ищет путь до всех вершин, если вы их как-то еще убираете, вы уже решаете другую задачу, ибо вы не ищите путь до убранных вершин. Для такой задачи A* или какие-то другие отсечения могут быть применимы.
Ну так и смысл функции в том чтобы учитывать прошлые ребра, прошли по A-B у вас путь B-C стал 10, прошли E-B у вас путь B-C стал 7. То есть важно откуда вы пришли.
Это нарушает принципы, на которых Дейкстра строится. Он перебирает вершины в порядке возрастания растояния и считает, что можно приписать новое ребро и путь изменится на фиксированную длину ребра. Потому что если в обрабатываемую сейчас вершину можно было бы прийти несколькими способами, может быть, взяв не самый короткий можно прийти в следующую вершину короче из-за изменчивости следующего ребра. И уже надо хранить все возможные пути в данную вершину и это уже не Дейкстра, а полный перебор с отсечениями. И все, вместо охренительно быстрого O(V log V + E) у вас O(V**V). И тут
Иногда такую задачу можно переформулировать в виде обычного графа с фиксированными ребрами: Для каждой вершины вы создаете кучу вершин - по одной на каждое входящее ребро и делаете из них ребра для каждого исходящего ребра нужной длины. Но это только если длина следующего ребра зависит только от одного предыдущего.
Я гуглом не пользуюсь лет 12 именно по причине отсутствия нормального поиска, ну и есть чаты с ИИ.
О боже, вам даже сам яндекс пишет "возможны неточности". Эти ИИ галюционируют. Но на будущее, не удивляйтесь, если ваши собеседники не будут в курсе, что за "иерархический" граф у вас.
это всё равно свойства (сумма свойств) характеризующие путь
Дейкстра накладывает важные требования на эти характеристики. Она требует: 1. Если к двум путям, заканчивающимся в одной и той же вершине приписать одно и то же ребро, то короткий путь все еще будет короче более длинного.
2. Если к пути приписать ребро, то он не может стать короче.
3. Если к двум путям одинаковой длины приписать одно и то же ребро, то итоговая длина будет одинаковой.
Именно на этих свойствах строистя алгоритм Дейкстры, именно по ним он позволяет себе хранить для каждой вершины лишь расстояние, а не весь путь, потом брать наиближайшую к началу вершину и через нее персчитывать пути к остальным вершинам. Эти свойства, очевидно, выполняются, если у вас все ребра имеют фиксированные и неотрицательные веса и вы просто считаете сумму для пути, как это делается в классических задачах на поиск кратчайшего расстояния в графе, для которых алгоритм и был придуман.
Нельзя взять произвольную функцию высчитывания длины пути, прикрутить ее к дейскстре, а потом ругаться, что дейкстра - плохой, медленный алгоритм. Вы его применили не там, не туда и не так, не понимая как он работает. При этом ругаясь на "всяких как вы", которые вам что-то там не так сказали. Я от вас лишь спустя несколько дней и кучу простыней текста узнал про такую вот маленькую незначительную деталь, что у вас не обычный взвешанный граф, а какая-то хитрая функция расстояния.
Зачем мне такой функционал? Мне не нужно вызывать функцию два раза, всё считается один раз.
У вас граф же не дерево? В вершины же можно прийти несколькими способами с предыдущих "уровней"? Судя по вашим картинкам выше это так. Обычная рекурсивная функция ходя по этим ребрам придет в одну и ту же вершину несколько раз. Но, если у вас функция расстояния от пути классическая аддитивная, то можно результат работы функции не считать второй раз, ведь он будет точно такой же. Именно так и работает динамическое программирование. Но, как вы пояснили, у вас все-таки какая-то сложная функция вычисления длины пути, так что этот метод тут не применим (Также, как и дейкстра).
Если у вас длина следующего ребра зависит только от одного предыдущего ребра, то вы еще можете применить тут дейкстру, построив обычный взвешанный граф на основе вашего. Иначе вы на вашем графе не можете запускать ни один из существующих алгоритмов поиска кратчайшего пути. Они на такое не рассчитаны вообще. Если вы там все-таки запустили дейкстру, то она каждую вершину может обрабатывать кучу раз и она действительно вырождается в перебор почти всех путей в графе. И поэтому работает так долго для такого маленького графа.
Единственный вариант решать вашу задачу через графы: у вас вершины в графе должны соответствовать всем возможным путям, и вам в этом очень большом графе надо запускать A* (не храня сам граф, конечно).
Там достаточно хорошая реализация самого алгоритма, но есть лишние проверки в интерфейсе, все-таки это довольно обобщенная реализация. Закомментируйте вызов HasEdge() в AddEdge().
Там обычная куча. Фиббоначиева куча теоретически быстрее, но на практике будет полезна только для очень больших графов. У вас, по описанию, не достаточно большой граф. И судя по тому, что вы говорили, что у вас Дейкстра все пути перебирала - у вас неправильная реализация.
Мне нужен оптимальный маршрут, по сути Дейкстра это и делает:
Дейкстра ищет кратчайший* маршрут, а не "оптимальный". Если у вас критерий оптимальности не тупо "сумма чисел на ребрах минимальна", то вам надо подумать прежде чем применять дейкстру. Вы писали, что у ребер есть какие-то свойства, которые влияют на то, можно ли по ним проходить - это звучит как противопоказание к Дейкстре. Если вы, таки, напишите наконец-то условие вашей задачи, я смогу вам точно сказать.
*Вообще, Дейкстра обобщается на целый класс функций расстояния, например, если у вас длина пути - это длина минимального ребра в пути. Но должны выполнятся особые свойства, чтобы алгоритм был применим. Пока вы не расскажите вашу задачу, и судя по тому, что у вас алгоритм выродился в перебор всех путей, как вы написали, нужные свойства не выполняются.
и как хитрость влияет на что-то? какая разница алгоритму переменная Weight является константной переменной INT или функцией, возвращающей INT?
Нет же, если у вас просто длина ребра как-то считается от фиксированных параметров, то это и есть фиксированная длина ребра и все ваши параметры - это лишь мишура и деталь реализации. Речь шла а том, что длина ребра может менятся, например, от того по каким ребрам вы прошли раньше. Или от времени.
Определение гуглится, не я же его придумал, я только использую.
Дайте, пожалуйста, ссылку, если вам не сложно. Я не нагуглил.
Вы про то что длина пути это сумма весов рёбер? А бывает иначе?
Конечно, бывает. Бывает как угодно. Скажем, у вас граф описывает дорожную сеть, и если вы по перекрестку прямо едете, то у вас "длина" следующего ребра короче, ибо вам тормозить не надо, а если вы поворачиваете, то вам еще надо скорость набрать. Бывает, что у вас граф представляет остановки общественного транспорта, и вам надо будет ждать следующего автобуса, так что тут длина следующего ребра зависит от того, в какое время вы оказываетесь в вершине, т.е. от длины предыдущего пути. Или у вас лабиринт с дверьми и ключами, и вы вообще не можете по какому-то ребру пройти, если не посетили вершину с нужным ключем до этого. А в каких-то задачах в качестве длины пути берут максимальное ребро в пути, а не сумму.
Именно про что-то такое я и думал, раз у вас там какие-то параметры и свойства ребер повылезали. Но похоже все гораздо проще. Это вы детали вашей передметной области тащите в граф, хотя они там не нужны. Высчитали вы длину ребра и все, можно про все ваши свойства забыть, это на алгоритм никак не влияет.
И вот мы пошли по A-B-C и приняли решение что C-E нам не нужно и убрали ребро. А C-D посчитали. Всё. Что не так? Ну умерла какая-то ветка, выкинули её. Это же простейшая оптимизация, мы так можем выкинуть до 99% графов, ну цель у нас такая или если не всё обсчитываю то это типа "низзя" никак? Почему нельзя? Кто так решил? Почему если я Дейкстре помогаю это уже не Дейкстра? Алгоритм же остаётся прежним и даже его реализация той же.
А если в графе есть ребро E-D? Вдруг оно короче будет? Вообще, раз вам можно какие-то вершины выбрасывать из графа, у вас задача поиска пути из одной вершины в другую, а не до всех? Это другая задача. Дейкстра лучший алгоритм, если вам надо найти путь до всех вершин в произвольном графе. Тут нельзя ничего выбрасывать.
Вообще, вы сказали, что динамическое программирование вам не знакомо, но в вашей задаче, похоже самым быстрым решением будет именно оно:
Рекурсивная функция, которая выдает кратчайшее расстояние до конца от заданной вершины. Функция сохраняет свой результат и при повторном вызове ничего не считает, а просто возвращает уже подсчитанный результат. Функция перебирает исходящие ребра, вызвается рекурсивно от концов и выбирает лучший вариант ребро+длина оставшегося пути. Если вариантов нет, то возвращает "бесконечность" (можно взять достаточно большое число, или возвращать -1. Только помните, что бесконечность+x=бесконечность).
Если вам нужна не только длина, но и весь путь, то функция еще дополнительно запоминает по какому ребру был кратчайший путь. Для восстановления пути надо от начальной вершины по этим сохраненным ребрам пройтись. Есть еще и нерекурсивная реализация с очередью.
Всякие альтернативные сборки хромиума. Там тупо нет компании, на чьи сервера можно лить данные.
А как же пропаганда одобрения и одобрение пропаганды экстремизма? А дискридетация армии? А распространение информации об обходе блокировок? Более того, там кого-то уже судили за публичные действия, потому прослушивающего личный разговор мента судья признал за публику. Так что если кто-то ваш host почитает и там, не дай бог, ересь какая-нибудь присутствует, вас уже могут посадить. Ведь нет оснаваний не доверять сотруднику, да и эксперт все что надо подтвердит. Плюс, список расширяется с умопомрачительной скоростью и рано или поздно даже попытки обхода блокировок будут караться.
Так что если вы еще не сидите, это не ваша заслуга - это их недоработка.
Случайно натренировали сетку определять красивые/симпатичные лица? Не секрет, что привлекательные люди живут на легком уровне сложности. Им много чего прощается, к ним более благосклонны окружающие, им дают больше шансов. В среднем такие люди более успешны чем некрасивые с такими же личностными качествами, навыками и знаниями.
Не может статья о сложной теме быть в полтора экрана без учета картинок. Краткость, конечно - сестра таланта, но тут не тот случай.
Спасибо, стало понятнее.Разделение дерева какими-то свойствами обладает? Например, в отсоединенном куске будут только элементы с меньшим приоритетом?
На одном уровне все элементы с заданным приоритетом?
Что значит родитель в этой парадигме? И зачем вам его брать? Дерево - это внутреннее устройство структуры. Вообще говоря, снаружи вы о том что там вообще дерево можете и не знать. В insert() у вас никакого понятия о родителях/детях нет.
В таком случае вам не нужно дерево. Вам достаточно std::unordered_map<int, vector<Data>> priority_to_data. И еще в нагрузку к этому vector<> всех приоритетов, которые в структуре есть, чтобы можно было быстро брать следующий, предыдущий приоритет.
С разделением на части только не понятно немного. Возможно каждый кусок будет иметь свой вектор приоритетов и шарить один unordered_map. Если надо совсем быстро, то vector приоритетов тоже будет общим, и каждый кусок будет хранть array_view какой-нибудь на него.
Нет, я имею ввиду описание того, что дерево делает. Какую задачу структура данных решает вообще. Я вам даже кучу примеров описания для других структур привел.
В бинарном дереве нет приоритетов. Приоритет есть в куче.
Ну вот никому ничего не понятно, потому что неясно, что это вообще за структура и что она делает, зачем она нужна. Вы какие-то детали рассказали, но вообще не те, которые нужны для этого рассказа.
Это уже баян. Сейчас модно доказывать гипотезу Коллатца.
Опять же. Нет такого термина. Его вам ИИ нагаллюционировал.
Как обычно бывает со многими "это очевидно" - автор не смог сам доказать.
Такое объяснение может дать интуицию того, что именно алгоритм делает. Может даже помогает его запомнить. Но без теорем, лемм, математической индукции и всей этой "скучной" мишуры вы не докажете, что алгоритм работает.
Почему вот тут, если одна девочка попробовала все "ребра", не нашла себе пару, к ней не надо больше никогда возвращатся? Ведь подобавляв других девочек мы что-то поменяем в рассадке, почему не может вдруг оказаться так, что вот та девочка без пары теперь сможет найти себе пару? Если это не так, то алгоритм был бы за O(N^2M), ведь после каждой перерассадки надо было бы опять проходится по всем девочкам без пары и запускать поиск.
Почему вы в dfs не зачищаете пометки после поиска от каждого ребра? Вот попросила девочка 3 мальчика 1 с ней сесть, он спросил девочку 1, та спросила мальчика 2, потом что-то и еще и не нашлось ничего. Почему вот тут девочка 1 даже не будет справшить мальчика 2 с ней сесть? Ведь теперь мальчик 1 не пытается с ней сесть, девочка 3 никуда от него не ушла, почему не надо запускать всю цепную реакцию опять?
Почему алгоритм вообще находит максимальное паросочетание? Почему обязательно найдется такая цепочка из девочек-мальчиков, увеличивающая количество пар, если паросочетание не максимально?
Еще, этот алгоритм - это алгоритм Куна, а не "венгерский". "Венгерским" называют другой алгоритм для поиска паросочетания минимальной стоимости ну или для решения задачи о назначениях.
Вообще нет. Абсолютно нет, как вы вдруг переключились на потоки? Это называется построение удлинняющей цепочки.
Если там вся книга такая, то могу лишь посоветовать никому ни при каких обстоятельствах к ней не приближатся вообще.
И еще, вы привели какие-то детали реализации касающиеся набора профилей, но ни ссылки на код, ни детального описания реализации нигде нет.
В статье очень не хватает хоть какого-то описания, что же это за структура данных-то и какие операции она выполняет.
Например, приоритетная очередь позволяет добавлять в структуру элементы с неким параметором "приоритет" и неким ключом, выдавать и удалять элемент с максимальным приоритетом и иногда изменять приоритет элемента с данным ключом: Insert(priority, key), GetMax() -> key, RemoveMax(), ChangePriority(key).
Бинарное дерево поиска позволяет добавлять элемент с ключом, удалять элемент по ключу и проверять, есть ли данный ключ в структуре, перебирать элементы в порядке возрастания ключа: Insert(key), remove(key), HasKey(key) -> bool, enumerate()-> key[]. Хеш-таблица далает все тоже самое, кроме перебора элементов по порядку возрастания ключа.
Дерево отрезков умеет изменять значение по индексу и выдавать сумму или максимум на отрезке между заданными индексами... и так далее.
Вот также надо расписать все ваши операции, без этого вообще непонятно, зачем нужна ваша структура и нужна ли она вообще. Что за приоритет, что там меняется вообще, а что неизменно? Может, ваши операции с такой же сложностью выполняются на обычном массиве или связном списке. Может, вам подойдет обычная сортировка подсчетом вместо какой-то структуры данных, если вам надо упорядочить "клетки" по приоритету.
В японии толстых почти нет. В первую очередь из-за общественного давления. Толстых там просто презирают и принято не выделятся из общества.
Вы читали ваши ссылки-то?
В первой статье иерархия исходит из строки, над которой строится граф, ведь подстроки можно организовать в некоторую иерархию по вложению. Это не какой-то тип графа. И там нет никакого определения иерархических графов.
По второй ссылке действительно есть некоторое определение, вот только оно к вашему графу не имеет никакого отношения. Там иерархия - это отдельная структура, заданная над графом - дерево, в которое организованы "фрагменты", подграфы исходного графа. При чем этому определению вполне подходят и графы с циклами, где нельзя, как вы говорите "выстроить вершины по уровням".
Третья - какой-то студент отсебятину какую-то написал.
Вам выше уже написали. Понимаю. Почитайте про свойство capacity у этого list. Пока добавляемые элементы помещаются в capacity, все происходит за O(1). Если нет, то вот тогда происходит реаллокация. Но трюк в том, что выделяемый размер примерно удваиваится. В результате, если вы в массив N раз чего-то добавили у вас суммарно будет выделено максимум 2N байт памяти за log(N) аллокаций и все элементы суммарно будут скопированы максимум 2N раз. Что дает в среднем O(1).
N обычно обозначают количество вершин, но ладно. Дейкстра выполняет O(V log V + E) операций. Но в графе O(V^V) путей. Не квадрат, а в степени. Если считать за N ребра, то путей получается O(sqrt(N)^sqrt(N)). Например полный граф, тут количесество путей - это все упорядоченные наборы разных чисел от 1 до V, ведь вы можете в каком угодно порядке обходить какие хотите вершины. Их O(V!). Так что дейкстра никак не может рассматривать все пути, их на много много порядков больше чем ребер. Еще раз аналогия - комбинаций в замке с N цифрами - 10^N. Но, если вы умеете по началу комбинации понимать правильная ли она, то вы можете подобрать код за 10*N операций. На много порядков быстрее, фиксирую правильные цифры слева на право. Вот и Дейкстра так же: вместо перебора всех путей, он перебирает только "начала" путей, фиксируя кратчайшие пути и продлевая их. Но это работает только если кратчайший путь в вершину V через U точно совпадает с кратчайшим путем в U в начале.
Нет. Еще раз, кодовый замок: Вы не перебираете комбинации, вы перебираете только одну цифру. Вот попробовали вы цифры 0-9 в самой первой позиции, услышали щелчек на цифре 7 - вы знаете, что код начинается с 7. Вы уже не будете перебирать 9*10^(N-1) комбинаций, начинающихся с любой другой цифры. Так же и дейкстра - он никогда не перебирает заведомо не оптимальные пути. Найдя один кратчайший путь в какую-то вершину он уже никогда не будет перебирать ни один путь, проходящий через эту вершину и не начинающийся точно так же. Именно так он среди O(V^V) путей находит лучшие всего-то за O(VlogV + V^2) операций.
У вас в одну и ту же вершину можно прийти разными способами. Это видно на картинке. И вы сами сказали, что длина следующего ребра из этой вершины зависит от всего пути, вы сами сказали.
Я так понимаю, количество бит, чтобы закодировать кусок данных, сответсвующий ребру, зависит от того, что у вас там в словаре уже раньше записано, а это определяется ребрами, по которым вы сюда пришли. И вполне может быть так, что записав ту же самую прошлую часть файла но менее оптимально, у вас можно следующий кусок закодировать гораздо компактнее. Это именно так коллизия, о которой я рассказал.
Но тогда длина ребра не зависит от того как вы в вершину пришли, почему вы говоли выше, что зависит? Вы же писали, что длина может быть разной:
Если же у вас для этих двух случаев будут разные вершины, то у вас вершины графа соответствуют различным путям в графе, и вы тут путаете два графа. В первом графе у вас вершины соответствуют, я полагаю, позициям в файле, а ребра - записи куска файла. Тут длина зависит от того, как вы в вершину пришли. И есть второй граф, где вы каждому возможному пути в первом графе ставите в соответстве вершину. Этот второй граф будет взвешанным, в нем длина ребра константна, и на нем можно запускать Дейкстру. Это именно тот граф, на котором я вам предложил запускать А*.
Ха, это решается онлайн системой для проверки заданий и уникальным одноразовым кодом для доступа к системе в каждом экземпляре. Еще можно каждый год чуть-чуть менять числа в задачах.
Проблема выпуска учебников (скорее даже методичек) только чтобы заработать - весьма распространена очень много где.
Есть мобильные шутеры, например call of duty, фортнайт. Есть выжывачи всякие, есть майнкрафт и куча других 3d игр от первого или третьего лица. Есь очень прилично выглядящие экшоны вроде genshin impact и прочих ААА донатных помоек.
Но не графонием одним игры богаты. Сейчас на ПК и консольках ААА игры выглядят зачастую не лучше того, что было лет 10 назад в основном. И современные смартфоны весьма мощные по тем временам. И есть очень красивые игры и на смарфтонах.
Геймплей можно и на смартфоны завезти, было бы желаение.
Управление в принципе на смартфоне работает для всех игр, в которые можно играть на геймпаде. Стратежки реального времени - да, вот в это на мобилках играть тяжко, так что их мало, но они есть. Хоть и не пользуются популярностью (а они и на "взрослых" платформах не пользуются популярностью).
Главная проблема мобилок, что там пользователей приучили донатить и все игры - донатные помойки, да казино для детей с лутбоксами и гачей.
Почитайте какую-нибудь книжку по структурам данных. Почитайте вашу же ссылку. Там написано: что этот List дает доступ по индексу. Ну и дальше в документации написано, что этот доступ идет за O(1). Так что это выглядит и крякает, как массив. Массив и есть. Динамический, правда, а не фиксированного размера, но от этого работа с ним не начинает тормозить. Максимум, там проверка выхода за границы массива. Вон, в С++ это называют vector. В java ArrayList.
На самом деле не дорого. Ассимптотически за O(1).
Ну я же попросил вас этот код в "задаче с дейкстрой" применить, а вы отказались, потому что у вас highload.
Тут разница как в переборе кода на кодовом замке целиком или по цифре. Дейкстра перебирает только одно ребро в пути, находит лучшее и фиксирует его. Как если бы вы в замке по какому-нибудь щелчку могли понять, что вот вы первую цифру правильно набрали. И в итоге вам для отгадывания N цифр надо 10*N попыток а не 10^N. Всех путей в графе экспоненциально много, поэтому дейкстра, которая работает за полиномиальное время никак не может их перебирать.
Поэтому надо разделять, что вы там перебираете - все пути, или все ребра, продолжающие оптимальный путь в данной вершине.
Скажите, как вы остекаете ребро даже не смотря на него? У вас какая-то особая структура графа, что вы в момент его построения можете заранее понять как не строить какие-то ребра? Причем сразу пачками? Если же у вас в коде есть хоть одна строчка, которая определяет, надо ли вот это ребро выкинуть, то вот вы уже на это ребро посмотрели. А сделали ли вы это один раз при отсечении ребра, или один раз внутри дейкстры - не особо большая разница.
Потом, у вас не столько отсечение ребер, сколько вы выбрасываете из рассмотрения какие-то вершины? Это значит, что у вас не задача найти пути до всех вершин, которую и решает лучше всего дейкстра, а задача найти путь до одной конкретной.
Вы понимаете, почему Дейкстра не работает, например, с отрицательными ребрами? Что в алгоритме сломается? Это же всего-лишь дополнительне условие!
Вот с изменением длин ребер в зависимости от прошлого пути сломается вот что:
Вот вы в алгоритме дейкстры делаете "релаксацию" ребра, когда обрабатываете какую-то вершину: если путь по ребру из вершины в следующую вершину короче чем то, что у вас записано, вы этот путь запоминаете как новый кратчайший. В обычных взвешанных графах вы тут просто берете и прибавляете длину ребра к пути. В вашем случае, раз у вас длина зависит от предыдущего ребра, вам надо взять весь путь. Ну и допустим в текующую вершину есть 2 пути, один длиной 10 через вершину A, другой длины 8 из вершины B. Вы запомните путь через B, так, ведь он короче?
Допустим ребро в следующую вершину будет длиной 10, если вы пришли из B и длиной 1, если вы пришли из А. Вот вы и начитаете путь длины 18 в следующую вершину, через B, хотя есть путь длины 11, через А. Потому что алгоритм дейкстры хранит только одно кратчайшее растояние до вершины, и пытается вот этот один кратчайший путь продолжить всеми ребрами.
Дейкстре важно, что этот int будет один и тот же независимо от того, как вы в вершину пришли. Зависит только от последней вершины в пути, и вершины в которую вы путь продолжаете. За счет этого допущения он позволяет себе фиксировать для каждой вершины один кратчайший путь и забывать про все остальные. Выше я привел пример, почему в вашем случае это делать нельзя. Может быть так, что кратчайший путь в вершину U + ребро UV не обязательно кратчайший путь в V через ребро UV. А это основной принцип на котором основан алгоритм - он хранит только кратчайший путь в каждую вершину. Потому что в взвешанных графах не важно, как вы в вершину пришли: если вам нужно получить кратчайший путь через вершину, вы можете просто продолжыть самый короткий путь в нее.
Это в нормальной дейскстре. В вашем графе может быть что угодно. Ибо, если запустить на вашем графе обычную реализацию, она найдет не оптимальный путь, а восстановление ответа вообще может зациклится.
Граф, где вершины - это все возможные пути - он слишком большой, чтобы его в память засунуть. Но A* не надо знать весь граф целиком для работы. Ему надо лишь уметь получать ребра исходящие из заданной вершины. Их можно генерировать на лету. Берете текущий путь, продолжаете всеми возможными способами, смотрите в какой-нибудь хеш-таблице, какой номер у вершины для получившегося пути. Если его там нет, назначаете следующий свободный номер. В результате весь этот расширенный граф не хранится, а хранятся только данные относящиеся к вершинам, которые алгоритм посетил. За счет отсечения A* посещает лишь малую долю вершин.
Вы запускали? Linq там используется только в hasEdge, который я попросил закоменнтировать и removeEdge, который вам не нужен. Да в выводе ответа. Это погрешности, даже если оно тормозит. А List<T> - это не список, а массив. Тормозит не сильнее vector в С++, который я всю жизнь использую даже на олимпиадах, где скорость ой как важна. Список в C# - это LinkedList.
Highload у вас, ха! С жалкими миллионами ребер. Highload, это когда данных столько, что надо запускать на кластере, ибо они в RAM одной машины не помещаются. И при этом надо выдавать ответ в течении миллисекунд. Это точно не ваш случай.
Опять у вас с терминологией проблемы. Перебирать все ребра - это не перебирать пути. Перебирать пути, это пробывать a->b->c->d, a->e->d, a->f->c->d... Путей в графе экспоненциально много. Ребра вам итак все придется просмотреть хотя бы по разу, а дейкстра именно столько раз их и смотрит. Меньше уже никак. Их отсекать смысла нет.
Дейкстра "убирает" вершины, до которых путь уже найден. Дейкстра ищет путь до всех вершин, если вы их как-то еще убираете, вы уже решаете другую задачу, ибо вы не ищите путь до убранных вершин. Для такой задачи A* или какие-то другие отсечения могут быть применимы.
Это нарушает принципы, на которых Дейкстра строится. Он перебирает вершины в порядке возрастания растояния и считает, что можно приписать новое ребро и путь изменится на фиксированную длину ребра. Потому что если в обрабатываемую сейчас вершину можно было бы прийти несколькими способами, может быть, взяв не самый короткий можно прийти в следующую вершину короче из-за изменчивости следующего ребра. И уже надо хранить все возможные пути в данную вершину и это уже не Дейкстра, а полный перебор с отсечениями. И все, вместо охренительно быстрого O(V log V + E) у вас O(V**V). И тут
Иногда такую задачу можно переформулировать в виде обычного графа с фиксированными ребрами: Для каждой вершины вы создаете кучу вершин - по одной на каждое входящее ребро и делаете из них ребра для каждого исходящего ребра нужной длины. Но это только если длина следующего ребра зависит только от одного предыдущего.
О боже, вам даже сам яндекс пишет "возможны неточности". Эти ИИ галюционируют. Но на будущее, не удивляйтесь, если ваши собеседники не будут в курсе, что за "иерархический" граф у вас.
Дейкстра накладывает важные требования на эти характеристики. Она требует:
1. Если к двум путям, заканчивающимся в одной и той же вершине приписать одно и то же ребро, то короткий путь все еще будет короче более длинного.
2. Если к пути приписать ребро, то он не может стать короче.
3. Если к двум путям одинаковой длины приписать одно и то же ребро, то итоговая длина будет одинаковой.
Именно на этих свойствах строистя алгоритм Дейкстры, именно по ним он позволяет себе хранить для каждой вершины лишь расстояние, а не весь путь, потом брать наиближайшую к началу вершину и через нее персчитывать пути к остальным вершинам. Эти свойства, очевидно, выполняются, если у вас все ребра имеют фиксированные и неотрицательные веса и вы просто считаете сумму для пути, как это делается в классических задачах на поиск кратчайшего расстояния в графе, для которых алгоритм и был придуман.
Нельзя взять произвольную функцию высчитывания длины пути, прикрутить ее к дейскстре, а потом ругаться, что дейкстра - плохой, медленный алгоритм. Вы его применили не там, не туда и не так, не понимая как он работает. При этом ругаясь на "всяких как вы", которые вам что-то там не так сказали. Я от вас лишь спустя несколько дней и кучу простыней текста узнал про такую вот маленькую незначительную деталь, что у вас не обычный взвешанный граф, а какая-то хитрая функция расстояния.
У вас граф же не дерево? В вершины же можно прийти несколькими способами с предыдущих "уровней"? Судя по вашим картинкам выше это так. Обычная рекурсивная функция ходя по этим ребрам придет в одну и ту же вершину несколько раз. Но, если у вас функция расстояния от пути классическая аддитивная, то можно результат работы функции не считать второй раз, ведь он будет точно такой же. Именно так и работает динамическое программирование. Но, как вы пояснили, у вас все-таки какая-то сложная функция вычисления длины пути, так что этот метод тут не применим (Также, как и дейкстра).
Если у вас длина следующего ребра зависит только от одного предыдущего ребра, то вы еще можете применить тут дейкстру, построив обычный взвешанный граф на основе вашего. Иначе вы на вашем графе не можете запускать ни один из существующих алгоритмов поиска кратчайшего пути. Они на такое не рассчитаны вообще. Если вы там все-таки запустили дейкстру, то она каждую вершину может обрабатывать кучу раз и она действительно вырождается в перебор почти всех путей в графе. И поэтому работает так долго для такого маленького графа.
Единственный вариант решать вашу задачу через графы: у вас вершины в графе должны соответствовать всем возможным путям, и вам в этом очень большом графе надо запускать A* (не храня сам граф, конечно).
Спасибо, но это не вообще не то, чего я просил. Там нет ничего про множество Мандельброта.
Это не общепринятый термин. Общепринятый - ориентированный ациклический граф. DAG по английски.
https://rosettacode.org/wiki/Dijkstra's_algorithm#C#
Там достаточно хорошая реализация самого алгоритма, но есть лишние проверки в интерфейсе, все-таки это довольно обобщенная реализация. Закомментируйте вызов HasEdge() в AddEdge().
Там обычная куча. Фиббоначиева куча теоретически быстрее, но на практике будет полезна только для очень больших графов. У вас, по описанию, не достаточно большой граф. И судя по тому, что вы говорили, что у вас Дейкстра все пути перебирала - у вас неправильная реализация.
Дейкстра ищет кратчайший* маршрут, а не "оптимальный". Если у вас критерий оптимальности не тупо "сумма чисел на ребрах минимальна", то вам надо подумать прежде чем применять дейкстру. Вы писали, что у ребер есть какие-то свойства, которые влияют на то, можно ли по ним проходить - это звучит как противопоказание к Дейкстре. Если вы, таки, напишите наконец-то условие вашей задачи, я смогу вам точно сказать.
*Вообще, Дейкстра обобщается на целый класс функций расстояния, например, если у вас длина пути - это длина минимального ребра в пути. Но должны выполнятся особые свойства, чтобы алгоритм был применим. Пока вы не расскажите вашу задачу, и судя по тому, что у вас алгоритм выродился в перебор всех путей, как вы написали, нужные свойства не выполняются.
Нет же, если у вас просто длина ребра как-то считается от фиксированных параметров, то это и есть фиксированная длина ребра и все ваши параметры - это лишь мишура и деталь реализации. Речь шла а том, что длина ребра может менятся, например, от того по каким ребрам вы прошли раньше. Или от времени.
Дайте, пожалуйста, ссылку, если вам не сложно. Я не нагуглил.
Конечно, бывает. Бывает как угодно. Скажем, у вас граф описывает дорожную сеть, и если вы по перекрестку прямо едете, то у вас "длина" следующего ребра короче, ибо вам тормозить не надо, а если вы поворачиваете, то вам еще надо скорость набрать. Бывает, что у вас граф представляет остановки общественного транспорта, и вам надо будет ждать следующего автобуса, так что тут длина следующего ребра зависит от того, в какое время вы оказываетесь в вершине, т.е. от длины предыдущего пути. Или у вас лабиринт с дверьми и ключами, и вы вообще не можете по какому-то ребру пройти, если не посетили вершину с нужным ключем до этого. А в каких-то задачах в качестве длины пути берут максимальное ребро в пути, а не сумму.
Именно про что-то такое я и думал, раз у вас там какие-то параметры и свойства ребер повылезали. Но похоже все гораздо проще. Это вы детали вашей передметной области тащите в граф, хотя они там не нужны. Высчитали вы длину ребра и все, можно про все ваши свойства забыть, это на алгоритм никак не влияет.
А если в графе есть ребро E-D? Вдруг оно короче будет? Вообще, раз вам можно какие-то вершины выбрасывать из графа, у вас задача поиска пути из одной вершины в другую, а не до всех? Это другая задача. Дейкстра лучший алгоритм, если вам надо найти путь до всех вершин в произвольном графе. Тут нельзя ничего выбрасывать.
Вообще, вы сказали, что динамическое программирование вам не знакомо, но в вашей задаче, похоже самым быстрым решением будет именно оно:
Рекурсивная функция, которая выдает кратчайшее расстояние до конца от заданной вершины. Функция сохраняет свой результат и при повторном вызове ничего не считает, а просто возвращает уже подсчитанный результат. Функция перебирает исходящие ребра, вызвается рекурсивно от концов и выбирает лучший вариант ребро+длина оставшегося пути. Если вариантов нет, то возвращает "бесконечность" (можно взять достаточно большое число, или возвращать -1. Только помните, что бесконечность+x=бесконечность).
Если вам нужна не только длина, но и весь путь, то функция еще дополнительно запоминает по какому ребру был кратчайший путь. Для восстановления пути надо от начальной вершины по этим сохраненным ребрам пройтись. Есть еще и нерекурсивная реализация с очередью.