Алгоритм Дейкстры за O(M log N) | Реализация на C++

Алгоритм Дейкстры позволяет находить кратчайшие пути от заданной вершины до всех остальных вершин. В данном видео мы реализуем алгоритм Дейкстры за O(M log N), где N - количество вершин, M - количество ребер.
Код: github.com/she...

[@it.alchemist]

const int Inf = 30000

[@alexanderbozhnyukrs1469]

Не знаю, прочитаешь ли ты комментарий, но я благодаря тебе понял все, что связано с этим алгоритмом. Спасибо большое и надеюсь, что у тебя все отлично!

[@mishelseashell]

Спасибо тебе огромное :)
Долго искала понятный урок про Дейкстру именно с приоритетной очередью и наконец-то нашла

[@MartinIden-hn7ld]

Спасибо за видео
Как и было сказано ранее, в самой матрице неверно рассчитано значение
"Из 3й вершины в 1ю за 2 еденицы веса, у вас 1 в таблице смежности"
Вот код без ручного ввода и использующий очередь с приоритетом с компаратором (не нужно будет исп-ть минус)
const int INF = 100000;
int main() {
// Входные данные, сам граф, начальная и конечные точки
vectorgraf = {
{0, 1, 1},
{4, 0 , 1},
{2, 1, 0}
};
int start = 2;
int end = 1;
start--;
end--;
// Вектор для расстояний, инициализация начальной вершины, очередь из пар, пуш стартового эл-та в очередь
vectordist(graf.size(), INF);
dist[start] = 0;
priority_queueq;
q.push(make_pair(0, start));
while (!q.empty()) {
int length = q.top().first;
int v = q.top().second;
q.pop();
if (length > dist[v]) continue;
for (int i = 0; i < graf.size(); i++) {
int to = i;
int len = graf[v][i];
if (dist[to] > dist[v] + len and len >= 0) {
dist[to] = dist[v] + len;
q.push(make_pair(dist[to], to));
}
}
}
cout

[@НикитаЗейденс-у4ф]

Огромное спасибо за объяснение, искал очень долго реализацию с очередью этой, наконец-то, спустя столько времени, я нашёл её

[@МаркАврелий-я9щ]

От третьей вершины к первому расстояние 2, на минуте 1:19

[@MathPTU]

девочке 10 лет, а она уже шарит

[@АлександрЧистяков-н4ц]

Если ты ты это читаешь, то знай, что видео топовое. Зря забросила

[@Женя-г2г7ь]

Из 3й вершины в 1ю за 2 еденицы веса, у вас 1 в таблице смежности

[@ЮТУБПЛЮС-ш3ь]

Скорей всего ошиблась, человеческий фактор

[@diibirovzzz5470]

Спасибо большое, а можно и флойда?

[@Хорошийпарень-у7х]

Очень долго, гораздо быстрее было бы, если бы вы складывали все посещенные вершины в какой-нибудь хэш-сет и каждый раз его проверяли.

[@дмитрийсенин-ф6к]

А если узлы не все со всеми ?

[@dreamteamsolo]

Здравствуйте ,можете объяснить почему сложность данного алгоритма именно MlogN,logN в приоритетной очереди получается ,а где ещё проход на M

[@funnyicecream8276]

подскажите как надо изменить программу, чтобы вектор заполнять матрицей весов из файла?

[@ТалгатУспанов-ы5ь]

А как сделать, чтобы выводилось расстояние от заданной вершины до всех оставшихся?

[@XOR1344]

Просто проходишся від 1 до н і виводиш d[i]

[@dol_6a_eb]

Женись на мне

[@bogdanshelomanov5668]

Очень плохо сделано, сделай себе граф, у которого 10к вершин, твой алгоритм пройдет все вершины, даже если путь нужен от 1 до 4, но все вершины не нужно смотреть, зачем

[@it.alchemist]

Bogdan Shelomanov, если ты не просмотришь все вершины, то просто можешь не найти кратчайший путь, а именно эту задачу мы и хотим решить. e-maxx.ru/algo/dijkstra_sparse

[@bogdanshelomanov5668]

@@it.alchemist можешь, достаточно посмотреть, что эта вершина является минимальной и немзменной

[@bogdanshelomanov5668]

@@it.alchemist если она минимальна, меньше она быть не может, посмотри как люди на бумаге делают, каждая итерация по новой вершине добавляет какую-то в наименьшую, наименьшая - это вершина, путь до которой самый минимальный среди посещенных вершин, исключая уже наименьшие до этого

[@bogdanshelomanov5668]

@@it.alchemist ruclips.net/video/tyQSgTytc4s/видео.html
Тут мужик вот показал как раз

[@it.alchemist]

Bogdan Shelomanov у меня точно такой же алгоритм, только я ищу минимум с помощью приоритетной очереди, поэтому сложность не O(N^2 + M), а O(MlogN)!