Re: Shortest paths in a huge random graph
- To: mathgroup at smc.vnet.net
- Subject: [mg85140] Re: Shortest paths in a huge random graph
- From: schandler at uh.edu
- Date: Wed, 30 Jan 2008 06:03:44 -0500 (EST)
- References: <fnn0f0$jjt$1@smc.vnet.net>
On Jan 29, 4:51=A0am, MarvelousTau <nightvi... at gmail.com> wrote:
> Now I need to calculate the single-source shortest path for every
> vertex in a huge undirected weighted graph. A function in the package
> Combinatorica can work out the result by giving an adjacent matrix,
> but the graph has 5000 vertice and it would be very slow to work out
> all the paths. So I think it would be better the final form is a list
> of triple like {source, dist, edge}
>
> It seems rule-based programming will work it out neatly, but I'm poor
> on the level. So anybody would give me some advice?
>
> XIEXIE!
GraphUtilities`GraphDistanceMatrix is the function you need. It works
faster than the Combinatorica routine.