Liniowy (???) algorytm odnajdujący ścieżki pomiędzy każdą parą wierzchołków w grafie
| e150 | 28.11.2005 20:06:33 | |
 | Czy jest (teoretycznie) możliwy LINIOWY algorytm odnajdujący ścieżki pomiędzy KAŻDĄ parą wierzchołków cyklicznego, skierowanego grafu? Pytam o teoretyczną możliwość, ponieważ praktycznym, najszybszym algorytmem jaki znam jest algorytm o złożoności obliczeniowej równej:  gdzie E – krawędzie, V – wierzchołki. ??? | |
| Kajoj | 28.11.2005 23:07:14 | |
| No coz nie slyszalem o liniowym algorytmie i na zdrowy rozsadek jest to nie mozliwe, jakby sobie to wyobrazic, bo niby w jaki sposob. Co to za algorytm, to o | |
?
Z tego co mnie sie wydaje to algorytm ma zlozonosc 
a algorytm Bellmana-Forda 
.| e150 | 01.12.2005 01:45:18 | |
| > Co to za algorytm? Algorytm o wymienionej złożoności obliczeniowej zaproponowali Panowie: Karger, Koller i Philips, oraz niezależnie McGeoch. Algorytm Bellmana-Forda O(n^3) i jak mniemam Dijkstry(n^2) służą do rozwiązywania problemu najkrótszych ścieżek z jednego źródła. Ja miałem na myśli algorytm rozwiązywania problemu najkrótszych ścieżek pomiędzy WSZYSTKIMI PARAMI wierzchołków. > No cóż, nie słyszałem o liniowym algorytmie i na zdrowy rozsadek jest to nie możliwe, jakby sobie to wyobrazić, bo niby w jaki sposób. Jeśli chodzi o problemu najkrótszych ścieżek z jednego źródła to LINIOWE rozwiązanie tego problemu zaproponował Thorup, Raman i jakiś polak, ale już nie pamiętam, muszę przejrzeć ACM. PYTANIE NADAL POZOSTAJE AKTUALNE. | |