Перейти к содержимому


* * * * * 4 Голосов

Алгоритм Дейкстра

графы крайтчайший путь

В этой теме нет ответов

#1 petuhovskiy

    Пользователь

  • Пользователи
  • PipPip
  • 15 сообщений
  • ГородВитебск

Отправлено 22 декабря 2011 - 14:01

Алгоритм Дейкстра, применяется для

*поиска кратчайших расстояний от одной вершины до всех остальных

*построения оптимальных маршрутов от одной вершины до всех остальных

Алгоритм Дейкстра

Дан ориентированный взвешенный граф. Для него вам необходимо найти кратчайшее расстояние от вершины 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К)
    Количество загрузок:: 536

Сообщение отредактировал Модератор: 22 декабря 2011 - 14:13

Yo





Количество пользователей, читающих эту тему: 1

0 пользователей, 1 гостей, 0 анононимных