Kürzeste Wege Algorithmus

[DaColonel]

Hi,
ich hab da was interessantes gefunden kürzeste wege algorithmus
SO, dieses Teil ist ja schon eigentlich nice, habs auch ausprobiert etc. doch wie lass ich sowas auf einen Graph mit sehr vielen Knoten anwenden?
Hier muss man eine Matrix erstellen

dist[MAX_NODES][MAX_NODES];

die schnell den Speicher sprengt, wenn man zehntausende Knoten hat.
Kann man das irgendwie optimieren?

~

[mmazal]

Stichwort: Adjazenzliste

[Skym0sh0]

Stichwort Boost Graph Library, da sind einige Shortest_Path-Algorithmen drin, eine Graph Implementierung und alles was man braucht.

[Kenner von boost]

boost.graph

[Nexus]

Von Boost.Graph rate ich ab, die API ist dank der exzessiven Generizität ziemlich benutzerunfreundlich.

LEMON ist eine nette Alternative, hier siehst du einen Überblick über Shortest-Path-Algorithmen.

[Skym0sh0]

Es ist sehr viel Einarbeitung notwendig, das ist richtig Nexus

[bcl]

Boost Graph ist bestimmt Turing complete.