Vi presenterar en experimentell studie av den enda källan kortaste vägen problem med icke-negativa kantvikter (NSSP) på storskaliga grafer med hjälp av den parallellt steg algoritm. Vi rapporterar resultat på Cray MTA-2, en multitrådad parallelldator. MTA-2 är ett high-end delat minne system som erbjuder två unika funktioner som hjälper en effektiv parallell implementering av oregelbundna algoritmer: förmågan att utnyttja finkornig parallellism, och låg-overhead synkronisering primitiver. Vår implementation uppvisar anmärkningsvärd parallell speedup jämfört med konkurrenskraftiga sekventiella algoritmer, för lågdiameter glesa grafer. Till exempel tar det mindre än tio sekunder på 40 processorer av MTA-2, med en relativ hastighet på närmare 30, att kliva på en riktad skalfri graf på 100 miljoner hörn och 1 miljard kanter. Så vitt vi vet är detta de första resultaten av ett kortaste vägproblem på realistiska grafer i storleksordningen miljarder hörn och kanter.
Det finns också ett genomförande av  på Cray MTA-2 av Madduri och Bader REF.
An experimental study of a parallel shortest path algorithm for solving large-scale graph instances
{'venue': 'In Workshop on Algorithm Engineering and Experiments (ALENEX', 'journal': None, 'mag_field_of_study': ['Computer Science']}