Software Engineering - shortest path for large graph

You are viewing an archived Text-only version of the thread. To view this thread in it's original format and/or if you want to reply to this thread please [click here]

Author

shortest path for large graph

michaelbyrd

2006-01-15, 1:01 am

shortest path for large graph

Ok im trying to create a shortest path table(s) for a large graph, around 100000 nodes, yes, 100000. Now if i use Dijkstras algorithm for 100k nodes its gonna take up 78 GIGABYTES of memory, which for obvious reasons is not possible. Is there another good way to get this done in less space? The reason Im doing is because of speed issues, eventually i want to run a simulation where it will be crucial for this to be precomputed.
Any, yes ANY ideas will be greatly appreciated...

welcome to: http://michaelbyrd.drivehq.com/

Sponsored Links