Optimizing Dijkstra for dense graph?

Posted by Jason on Stack Overflow See other posts from Stack Overflow or by Jason
Published on 2009-09-12T00:31:53Z Indexed on 2010/06/05 15:02 UTC
Read the original article Hit count: 228

Filed under:

path

|

graph

|

dijkstra

|

shortest

Is there another way to calculate the shortest path for a near complete graph other than Dijkstra? I have about 8,000 nodes and about 18 million edges. I've gone through the thread "a to b on map" and decided to use Dijkstra. I wrote my script in Perl using the Boost::Graph library. But the result isn't what I expected. It took about 10+ minutes to calculate one shortest path using the call $graph->dijkstra_shortest_path($start_node,$end_node);

I understand there are a lot of edges and it may be the reason behind the slow running time. Am I dead in the water? Is there any other way to speed this up?

© Stack Overflow or respective owner

Related posts about path

get the path of moved directory/file (source path and destination path)

as seen on Ask Ubuntu - Search for 'Ask Ubuntu'
When one directory is moved to other destination path, then i want to log the entry of original source path and entry of the path where it moved. any command is already available ? or any other way of doing this task? Ex: D1 = /home/user/Documents/test D2 = /home/user/Documents/Data/test when… >>> More
Converting a URI path to a relative file system path in .NET

as seen on Stack Overflow - Search for 'Stack Overflow'
How do I convert an absolute or relative URI path (e.g. /foo/bar.txt) to a corresponding relative file system path (e.g. foo\bar.txt)? >>> More
BASH: Convert absolute path into relative path given a current directory

as seen on Stack Overflow - Search for 'Stack Overflow'
absolute="/foo/bar" current="/foo/baz/foo" # magic relative="../../bar" Can you help me with magic? (Hopefully not too complicated code...) >>> More
How to read from path in wpf comboboxitem and write into path of binding

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I tried to make up an example to show my problem. My combobox has a list of objects as itemssource. In my example it's a list of Persons. In the combobox i want to show the first name and the last name of the person. But i want to save the last name of the person in the "owner" property of… >>> More
Changing an xcode project Path with lowercase path issue

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a problem with an Xcode project which has a path of "/users/me/blah" with a lowercase 'u'. When I check my other projects (in the General Tab of the Project Info Window the Path starts with a uppercase "Users". This causes a couple of problems. When I try and add an existing file which is… >>> More

Related posts about graph

C++: Error in Xcode; "Graph::Coordinate::Coordinate()", referenced from: ...

as seen on Stack Overflow - Search for 'Stack Overflow'
In a program I am writing, I wrote for two classes (Coordinate, and Graph), with one of them taking the other as constructor arguments. When I try to compile it I get the following error for Graph.cpp: Undefined symbols: "Graph::Coordinate::Coordinate(double)", referenced from: Graph::Graph()… >>> More
How to create Line Graph and Bar graph on same parameters in asp.net

as seen on C# Corner - Search for 'C# Corner'
We can use GDI+ to draw chart components in C# or VB.NET language in memory and once the components are drawn in memory, we can save the drawing in an image on the Web server. Once the image is saved, we can display this image in an ASP.NET page using any Image tag or image control. >>> More
Display Graph using Boost Graph Library

as seen on Stack Overflow - Search for 'Stack Overflow'
Can anyone please tell me that once I've created a graph using Boost Graph library, how can I display that graph? My biggest concern is that the edge weights are coming from an exernal data source over the network. And I need to be able to display the edgeweights live as they get updated. >>> More
Matlab multiple graph types inside one graph

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I have a task to draw electrostatic field between two electrodes( at given sizes and shape ), what i have now is that i draw the electrodes with area plot (area(elect_x,elect_y)) the graph looks like this: ------------------.--- |.. .---. |.. |...| |… >>> More
[C++] Write connected components of a graph using Boost Graph

as seen on Stack Overflow - Search for 'Stack Overflow'
I have an file that is a long list of weighted edges, in the following form node1_id node2_id weight node1_id node3_id weight and so on. So one weighted edge per line. I want to load this file into boost graph and find the connected components in the graph. Each of these connected components… >>> More