подскажите поиск оптимального пути на графе с помощью алгоритма Флоида!!!!!

напишите хотябы в какои книге его можно наити или может он имеет еще одно название!!!!!!!!!   

набираем "Флойд" в строке поиска, которая сверху первого сообщения справа и нажимаем Go
получаем список тем
он не такой уж и большой, его можно просмотреть...
P.S.
после беглого просмотра, показалось, что кое-что может быть в этой теме:
http://forum.vingrad.ru/topic-54334/hl/%25...25B4/index.html

Может разберешься?
Var i,j,n:integer;
    g:array[1..100,1..100] of integer;

Procedure Init;
 Begin
  Assign(input,'input.txt');
   Reset(input);
    Readln(n);
     For i:=1 to n do
      For j:=1 to n do
       Read(g[i,j]);
   Close(input);
 End;

Procedure Solve;
Var k:integer;
 Begin
  For k:=1 to n do
   For i:=1 to n do
    For j:=1 to n do
     if (g[i,j]>g[i,k]+g[k,j]) and (g[i,k]>0) and (g[k,j]>0) Then g[i,j]:=g[i,k]+g[k,j];
 End;

Procedure Done;
 Begin
  Assign(output,'output.txt');
   Rewrite(output);
  For i:=1 To n do begin
   For j:=1 to n do
    Write(g[i,j],' ');
    Writeln;
  End;
   Close(output);
 End;

Begin
 Init;
 Solve;
 Done;
End.

еще и в гугле можно было найти че нить...

неопнимаю таких вопросов....как тебе его подсказать-открой лекции по дискретке...там все отлично написанно и понятно...капец

ip127001, если нужна книжка, то глянь книгу Стивена С. Скиены и Мигеля А. Ревиллы «ОЛИМПИАДНЫЕ ЗАДАЧИ ПО ПРОГРАММИРОВАНИЮ. Руководство по подготовке к соревнованиям» (Steven S. Skiena, Miguel A. Revilla. «PROGRAMMING CHALLENGES. The Programming Contest Training Manual»). 

Скачать электронную версию (5,5 Мб)


Это сообщение отредактировал(а) V.A.KeRneL - 23.1.2007, 14:23

Внимание вопрос, как оптимизировать флойда для графа из 1000 вершин...???

Чавой?

2esperant0: Дан граф, кол-во вершин <= 1000. Дано кол-во запросов t, t <= 100. Вид запроса: <name1> <name2>, где name - имя города. задача: вывести минимальнуй цену переезда из городов, указанных в запросах(в отдельных строчках). \\Запросы сделанны, чтобы никто не додумался решать дэйкстрой.

Это сообщение отредактировал(а) comp - 24.1.2007, 19:52

Так как в вашем премере все известно. Кроме того какие будут сделана запросы. То в  принципе решение распадется на два этапа 1)preprocessing 2)ответ на запрос.


Соответсвенно временная сложность будет - двойкой (x,y) когда х это сложность препроцесинга а у - сложность запроса.


Например решение флойдом дает (сложность Флойда,O(1))

Решение дайкстрой дает (O(1), сложность дайкстры)


Как вы видете эти два решения не сравнимы. 


какой ответ вам нужен?

2esperanto: сложность флойда O(1)?)))))Кто вам такое сказал?)))По-видимому O(N^3), где N - кол-во вершин графа. Сложность дэйкстры также O(1)?!)))Это уже что-то невероятное... самая простая реализация - O(N*M)... насколько я помню... ну да... вытаскивание из очереди сделаем за N... ну и релаксация... кол-во смежных вершин... а... точнее O(N*N)... вот... ну ни как не O(1)... ну и можно догадаться сделать очередь с приоритетами... на основе куч... двоичных... в итоге, мы минимальную вершину будем вытаскивать за O(Log(V))... ну создание кучи, очевидно, за O(V)... в итоге имеем что-то типа O(V*Log(V))... ну и очевидно, при таких ограничениях ни один из алгоритмов не проходит...

Это сообщение отредактировал(а) comp - 25.1.2007, 19:25

Товарищ Comp!!Вы не разглядели запятую в посте товарища esperanto. Имелось в виду следующее:
сначала проводим предобработку(В первом случае - Флойд) за сложность Флойда (т.е. за куб) а потом за константу отвечаем на каждый запрос.

Что касается дейкстры... запуская её для каждого запроса получаем время около t*n^2... А дальше всё зависит от TL в этой задаче... если порядка 3-5 сек... может быть и проскочит... 

Ну и конечно запоминать уже найденные пути и не искать их каждый раз и т.д.

И если возможно - выложите условие задачи как оно есть в оригинале...

2Strannik: Вот условие, http://www.spoj.pl/problems/SHPATH/

Вершин не 1000 а 10000... 

Если есть надежда что граф разреженный - реализуем для каждого запроса Дейкстру за О(ElogV) , ну и можно попробовать реализацию дейкстры за O(VlogV+E). Экспериментируй в общем.

Это всё уже давно испробованно...

И реализация за О(ВлогВ+Е) валится по тайму?

Да-да... не зря её решило очень мало народу... там что-то ну прямо очень не тривиальное...

Я уже встречался с подобным... Это как раз самое плохое... Задача вроде на стандартынй алгоритм, но не лезет по времени. На Тимусе была задача про нахождение макс. общей подпосл. в строках длинной до 200000 символов.
Будем думать, я у преподов спрошу. Елси что-нибудь нарою - сообщу...

200000 символов - это конечно круто... а у неё какой номер?