Efektyvi paieška grafe

Turiu grafą su ~50000 viršunių ir ~3500000 kraštinių, grafas orientuotas. Reikia surasti visus keliųs iš viršunės A į viršunė B. Keliams surasti naudoju rekursiją. Įmanoma kažkaip padaryi efektyvesne paieška, kad greičiau veiktų? ar pirkti galingesnį PC?

O tai nenori pasidalinti su kitais, kaip dabar ieškai? Nes vien tai, kad naudoji reuksiją, visiškai nieko nesako.

Ir iš vis, kam tau to reikia? Gal užtektų tik kelių skaičiaus?

O tai nenori pasidalinti su kitais, kaip dabar ieškai? Nes vien tai, kad naudoji reuksiją, visiškai nieko nesako.

 

Ir iš vis, kam tau to reikia? Gal užtektų tik kelių skaičiaus?

       static void FindPaths(string S, string E, double weight, List<KeyValuePair<string, double>> Path, BidirectionalGraph<string, Edge<string>> graph)
       {           
           if (S.Equals(E))
           {
               Path.Add(new KeyValuePair<string, double>(S, weight));
               for(int i = 0; i < Path.Count; i++)
                   Console.Write(Path[i].ToString()+" ");
               Console.Write("\n");
               Path.RemoveAt(Path.Count - 1);
               return;
           }
           if (Path.Contains(new KeyValuePair<string, double>(S, weight)))
               return;

           Path.Add(new KeyValuePair<string, double>(S, weight));

           var K = graph.OutEdges(S).GetEnumerator();

           while (K.MoveNext())
           {
               weight = K.Current.Weight;
               FindPaths(K.Current.Target, E, weight, Path, graph);
           }
           Path.RemoveAt(Path.Count - 1);
       }

Reikia man surasti visus įmanomus ryšius tarp duotųjų viršūnių

1. List<KeyValuePair<string, double>> Path;
   ...
   Path.Contains(new KeyValuePair<string, double>(S, weight))
   

   
   Šitą vietą būtų galima pagreitinti. Keliui naudoji sąrašą, o paieška sąraše proporcinga sąrašo dydžiui O(n). Jeigu naudotum aibę (Set), tai paieška truktų logaritminį laiką O(log n).
   

2. Savo kode tu perrenki visus galimus kelius. Pavyzdžiui, jei grafe yra koks atsišakojimas, į kurį patekęs niekad nepasieksi tikslo, tai į jį vis aplankysi ir aplankysi. Galėtum tokius atsišakojimus atmesti.
   
3. O šiaip tai čia pakankamai sudėtinga užduotis. Šiek tiek paieškojus internete nepavyko rasti kokio nesudėtingo ir spartaus algoritmo. Manau, kad šitai užduočiai spręsti šitie duomenų kiekiai per dideli.
   

patobulinau, pritaikiau 'Hoffman and Pavley K-shortest path algorithm.' pasinaudojus QuickGraph biblioteka, bet manajam grafui kelius skaičiuoja visvien amžinybė.. tai aš nesuprantu kaip pvz GPS randa kelią tarp dviejų taškų, kad ir Europos žemėlapyje? ten viršunių tikrai daugiau nei 50000, o ir GPS`e neįmontuotoas superkompiuteris, tai kas gali paiiškint? :D

Noreciau pasitikslinti ar tu nori surasti geriausia kelia t.y. pabuti GPS (1) ar nori surasti visus imanomus kelius (2)?

1) Jeigu geriausia kelia, tada siulau pasiskaityti apie Heuristic Search (puiki knyga: http://www.amazon.com/Artificial-Intelligence-Modern-Approach-Edition/dp/0136042597 ).

2) Visu imanomu keliu suradimas grafe yra np-hard problema, t.y. nera greito budo surasti ju. Taip, galima gan stiprokai paspartinti palyginus su dabartiniu tavo algoritmu, bet tai vistiek bus leta.