Алгоритм Дейкстра, применяется для
*поиска кратчайших расстояний от одной вершины до всех остальных
*построения оптимальных маршрутов от одной вершины до всех остальных
Алгоритм Дейкстра
Дан ориентированный взвешенный граф. Для него вам необходимо найти кратчайшее расстояние от вершины S до вершины F.
Входные данные
В первой строке записаны три числа N S F , N - кол.во вершин в графе, В следующих N строках записаны по N чисел - матрица смежности графа, где число в i-ой строке j-ом столбце соответствует ребру из i в j: -1 означает отсутствие ребра между вершинами, а любое неотрицательное целое число (от 0 до 100) - наличие ребра данного веса . На главной диагонали матрицы всегда записаны нули.
Выходные данные
Необходимо вывести искомое расстояние или -1, если пути между указанными вершинами не существует.
Ввод
3 1 2
0 -1 2
3 0 -1
-1 4 0
Вывод
6
Программный код
var f,n,s,i,j,min,p,nmin : longint; a:array [0..1000,0..1000] of longint; flag,pred,d : array [0..1000] of longint; begin readln(n,s,f); //Вводится кол-во вершин, начальная вершина, конечная вершина for i:=1 to n do begin flag[i]:=0; // Обнуляется массив флагов pred[i]:=0; //Обнуляется массив предков с помощью которого можно создать дерево end; for i:=1 to n do for j:=1 to n do begin read(a[i,j]); // Считываем элемент матрицы смежности if a[i,j]=-1 then a[i,j]:=maxlongint div 2; // Если нет ребра от i до j то заполняем максимом end; p:=s; //Номеру текущей вершине присваеваем начальную вершину flag[s]:=1;//Флагу начального элемента присваеваем 1 for i:=1 to n do d[i]:=a[s,i]; //Первоночальное заполнение массива for i:=1 to n-1 do begin min:=maxlongint div 2; //Минимальному присваеваем максимальное значение Nmin:=1; //Номеру минимального присваеваем номер 1 for j:=1 to n do //Ищем подходящий элемент if (flag[j]=0)and(d[j]<min) //Элемент более подходит если его флаг 0 и путь туда короче then begin min:=d[j]; //Минимальному присваеваем новый элемент Nmin:=j; //Номеру минимального присваеваем номер элемента end; p:=nMin; //Номеру текущей вершины присваеваем номер минимального элемента flag[p]:=1; //Флагу текущей вершины присваеваем 1 for j:=1 to n do if (flag[j]=0)and(d[j]>d[p]+a[p,j]) //Если флаг нового элемента 0 и старый путь длиннее нового then begin D[j]:=D[p]+a[p,j]; // Присваеваем новый путь pred[j]:=p; //Присваеваем предка end; end; if d[f]>=maxlongint div 2 then writeln(-1) else writeln(d[f]); //Если пути нет выводим -1 иначе выводим длину пути end.
Чтобы открыть файл измените расширение на *.pas
Коментарии во Free Pascal из файла будут абракадаброй так что читайте тут.
Артур молодец, только научись пожалуйста оформлять тему, а так хорошая работа, держи 5 звезд за тему!
Прикрепленные файлы
-
Deikstra.zip (1,73К)
Количество загрузок:: 537
Сообщение отредактировал Модератор: 22 декабря 2011 - 14:13