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


Задача

1/14

Дейкстра: Начало (C++)

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

Дан ориентированный или неориентированный взвешенный граф с n вершинами и m рёбрами. Веса всех рёбер неотрицательны. Указана некоторая стартовая вершина s. Требуется найти длины кратчайших путей из вершины s во все остальные вершины, а также предоставить способ вывода самих кратчайших путей.
 
Эта задача называется "задачей о кратчайших путях с единственным источником" (single-source shortest paths problem).

Выполняет такие же задачи как и 1-K BFS, но без учета K. Также как и 1-K BFS не умеет правильно обрабатывать отрицательные ребра

Алгоритм:
Сам алгоритм Дейкстры состоит из N итераций. На очередной итерации выбирается вершина V  с наименьшим расстоянием до нее из еще не отмеченных вершин, данная вершина становится отмеченной и из нее происходят релаксации соседних вершин.


 итоговая асимптотика алгоритма составляет: O(n2+ m)

Задача

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

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