Модуль: Алгоритм Дейкстры


Задача

8/14

Алгоритм Дейкстры за O(M logN) c set: Начало (C++)

Теория Нажмите, чтобы прочитать/скрыть

Так как асимптотика наивной реализации алгоритма Дейкстра: \(O(n^2 + m)\), то с увеличением количества вершин скорость работы становиться неудовлетворительной.
 Для улучшения можно использовать различные структуры данных: Фибоначчиевы кучи, множества set или очередь с приоритетом priority_queue. 
Рассмотрим пример с set, в результате итоговая асимптотика получается: \(O(n log (m))\), подробнее.

Задача

Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой.
 
Входные данные
В первой строке содержатся три числа: N, M, S и F (1≤ N≤ 100, 1≤ S, F≤ N), где N – количество вершин графа, M – количество ребер,  S – начальная вершина, а F – конечная. В следующих N строках вводится по N чисел, не превосходящих 100, – матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы записаны нули.
 
Выходные данные
Требуется вывести искомое расстояние или -1, если пути между указанными вершинами не существует.

Примеры
Входные данные Выходные данные
1 4 4 3 4
3 1 3
1 2 3
2 4 3
3 4 10
9