Печать кратчайшего пути из матрицы последовательности вершин (Алгоритм флойда)

@Mike · Регистрация: 20.01.2009

Author24 — интернет-сервис помощи студентам

Здравствуйте, проблема следующая:
не могу получить список вершин из результирующей матрицы. В книге "Структуры данных и алгоритмы" приведен пример алгоритма Флойда, на входе матрица представляющая граф:
0 8 5
3 0 ∞
∞ 2 0
на выходе результирующая матрица(P) представляющая матрицу кратчайших путей всего графа:
0 3 0
0 0 1
2 0 0.
В книге путь выводится с помощью функции path:

Pascal

procedure path (i,j:integer);
var
   k:integer;
   begin
k:=P[i,j];
if  k=0 then  return;
path(i,k);
writeln(k);
path(k,j);
end;{path}

К примеру, если требуется вывести путь из 1й вершины в 3ю, то функция сразу прекращает выполняться тк P[i,j] равно 0.
Помогите разобраться с этой проблемой, а то я уже весь день сижу, смотрю и ничего не пойму, то ли я туплю, то ли в книге косяк

@MiniMin · 22.06.2009, 10:27

неправильная у тебя матрица на выходе флойда получилась. ищи косяк в алгоритме... да и процедура вывода пути какая-то странная....
Я так понял здесь не стандартый алгоритм флойда, и в матрице P записаны не кратчайшие расстояния, а след. вершина в кратчайшем пути (исходя из процедуры path). напиши флойда как он там у тебя записан.

@Doc.X · 23.06.2009, 20:41

Аллгоритм у тебя действительно какойто стрёмный.

Могу дать ссылку на стандартную реализацию .. может поможет
Флойд

@Mike · 25.06.2009, 16:33 **[ТС]**

спасибо за советы, но я уже сам разабрался(нашёл чью-то прогу на паскале) и переделал под себя

, вот сама функция печати кратчайшего пути(итерационный метод), может быть ещё кому-нибуть пригодится:

C++

String^ GetPath(int i/*начало*/,int j /*конец*/)
       {
           int k;
           List<int>^ listNodes=gcnew List<int>();
           String^ strPath="";
           strPath+=String::Format("Длина пути: {0}\nПуть:\n",length->GetValue(i,j));
           while(i!=j)
           {
               k=(int)path->GetValue(i,j);
               listNodes->Add(j+1);
               j=k;
           }
           strPath+=String::Format("{0}",i+1);
           listNodes->Reverse();
           for each(int i in listNodes)
           {
               strPath+=String::Format(" --> {0}",i);
           }
           
           return strPath;
       }

@Only_HED · 14.07.2009, 17:18

http://e-maxx.ru/algo/Алгоритм флойда

@legi · 23.10.2009, 01:30

а можно весь код программы посмотреть?
что такое

C++

1	k=(int)path->GetValue(i,j);

@SerchLebid · 14.03.2011, 19:25

да а можете скинуть листинг проги?

@MiniMin 68 / 24 / 2 Регистрация: 16.05.2009 Сообщений: 73
	22.06.2009, 10:27	2
	неправильная у тебя матрица на выходе флойда получилась. ищи косяк в алгоритме... да и процедура вывода пути какая-то странная.... Я так понял здесь не стандартый алгоритм флойда, и в матрице P записаны не кратчайшие расстояния, а след. вершина в кратчайшем пути (исходя из процедуры path). напиши флойда как он там у тебя записан. 0

@Doc.X 11 / 11 / 0 Регистрация: 23.06.2009 Сообщений: 8
	23.06.2009, 20:41	3
	Аллгоритм у тебя действительно какойто стрёмный. Могу дать ссылку на стандартную реализацию .. может поможет Флойд 0

@Only_HED 5 / 5 / 2 Регистрация: 28.05.2009 Сообщений: 29
	14.07.2009, 17:18	5
	http://e-maxx.ru/algo/Алгоритм флойда 0

@SerchLebid 1 / 1 / 0 Регистрация: 04.10.2010 Сообщений: 31
	14.03.2011, 19:25	7
	да а можете скинуть листинг проги? 0

Опции темы