Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Алогоритм Флоида

Автор: flor_master 30.10.2006, 20:27

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

Автор: flor_master 31.10.2006, 16:17

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

Автор: maxim1000 31.10.2006, 16:24

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

Автор: baye 22.1.2007, 21:47

Может разберешься?
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.

Автор: Rodman 22.1.2007, 23:20

еще и в гугле можно было http://khpi-iip.mipk.kharkiv.edu/library/datastr/book_sod/kgsu/din_0124.html че нить...

Автор: ip127001 23.1.2007, 10:58

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

Автор: V.A.KeRneL 23.1.2007, 14:20

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

http://slil.ru/23605838 (5,5 Мб)

Автор: comp 24.1.2007, 17:25

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

Автор: esperant0 24.1.2007, 19:34

Цитата(comp @ 24.1.2007, 17:25)

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

Чавой?

Автор: comp 24.1.2007, 19:50

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

Автор: esperant0 25.1.2007, 10:36

Цитата(comp @ 24.1.2007, 19:50)

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

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

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

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

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

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

Автор: comp 25.1.2007, 19:22

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))... ну и очевидно, при таких ограничениях ни один из алгоритмов не проходит...

Автор: Strannik 25.1.2007, 22:41

Цитата

сложность флойда O(1)?)))))Кто вам такое сказал?)))По-видимому O(N^3),

Цитата

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

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

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

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

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

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

Автор: comp 26.1.2007, 08:23

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

Автор: Strannik 27.1.2007, 21:44

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

Цитата

n [the number of cities <= 10000]

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

Автор: comp 28.1.2007, 20:31

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

Автор: Strannik 28.1.2007, 22:00

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

Автор: comp 28.1.2007, 22:27

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

Автор: Strannik 28.1.2007, 23:00

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

Автор: comp 29.1.2007, 18:04

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