Задача "Дейкстра"
Дан ориентированный взвешенный граф. Для него вам необходимо найти
кратчайшее расстояние от одной заданной вершины до другой.
Входные данные:
В первой строке входного файла три числа: N, S и F (1 <= N <= 100;
1 <= S, F <= N), где N - количество вершин графа, S - начальная
вершина, а F - конечная. В следующих N строках по N чисел - матрица
смежности графа, где число в i-ой строке j-ом столбце соответствует
ребру из i в j: -1 означает отсутствие ребра между вершинами,
а любое неотрицательное число - присутствие ребра данного веса.
На главной диагонали матрицы - всегда нули.
Выходные данные:
Вывести искомое расстояние или -1, если пути между указанными
вершинами не существует.
Пример входного файла:
3 1 2
0 -1 2
3 0 -1
-1 4 0
Пример выходного файла:
6
Описание алгоритма Дейкстры.
Храним массив кратчайших уже найденных путей до каждой из вершин.
Вначале расстояние до начального элемента - 0, до остальных - бесконечность
N раз повторяем шаг алгоритма:
1) Находим вершину, из которой мы еще не ходили, и в расстояние до которой
минимально
2) Ходим из этой вершины, т.е.:
-Проверяем, если расстояние до данной вершины + ребро из нее в какую-то другую
вершину меньше, чем расстояние до той вершины, уменьшаем расстояние до
той вершины
-Помечаем, что мы походили из этой вершины.
После окончания мы получим массив кратчайших путей.
|
