Message Boards Message Boards

0
|
3583 Views
|
6 Replies
|
4 Total Likes
View groups...
Share
Share this post:

[Solved] Obtain the shortest paths in weighted graph efficiently?

Posted 3 years ago

POSTED BY: Richard Frost
6 Replies

Thanks to Daniel and Rohit for the tips ... which also led to the discovery of the WeightedAdjacencyGraph[] constructor. Here's what I discovered from some tests with my data ... all times local on a 5 yr-old Windows 10 box.

125 vertices, 7750 undirected weighted edges.
Unweighted graph, Graph[edges] ? 0.006 sec.
Weighted graph by list of weights Graph[vertices, edges, EdgeWeight -> edgeWeightsList] ? 0.006 sec.
Weighted graph by WeightedAdjacencyMatrix[vertices,weightedAdj] ? 0.05 sec.
Weighted graph by rules (e -> w) Graph[vertices, edges, EdgeWeight -> edgeWeightsRules] ? 1.8 sec.
Weighted graph by Annotation, Graph[annotatedEdges] ? 3.5 hours.

All the weighted graphs above have equivalent WeightedAdjacencyMatrix's, but the specialized constructor produces a graph containing self-edges that are infinitely weighted, so its graph object is not equal to the others.

Here's my test code, excluding the last one which ran overnight in a separate notebook.

POSTED BY: Richard Frost

What specifically do you do to find the paths? Are you computing paths between all vertex pairs?

POSTED BY: Daniel Lichtblau

Daniel, I would like to compute about 2 dozen shortest paths within weighted graphs. The textbook approach is to compute the weighted edges and the weighted edge graph as shown above, then apply

 wePath = FindShortestPath[weG,v1,v2];

However, the computation of weG by Graph[] appears intractable for some graphs of interest.

Is there a more efficient route to finding the few shortest paths?

POSTED BY: Richard Frost

I am still confused. Is the bottleneck the creation of the Graph objects? Or is it the application of FindShortestPath once they have been created?

--- edit ---

Sorry, I was not reading carefully. It is graph creation that is slow. I wonder if it might be more efficient to work directly with the sparse matrices that contain the edge weight information?

--- end edit ---

POSTED BY: Daniel Lichtblau

A complete graph of N vertices has N(N-1)/2 undirected edges. The matrix representation is not sparse. But I'll run some trials later on this morning for comparison.

Meanwhile, I'm wondering if there is someone at Wolfram who has encountered this situation before and found a better route?

POSTED BY: Richard Frost
Posted 3 years ago

Hi Richard,

It seems like specifying the edge weights using Annotation causes the performance issue with creating the graph.

g = CompleteGraph[30];
edges = EdgeList@g;
weightedEdges = Annotation[#, EdgeWeight -> 1] & /@ edges;

(g1 = Graph[weightedEdges];) // Timing
(* 2.60342, Null} *)

(g2 = Graph[edges, EdgeWeight -> ConstantArray[1, Length@edges]];) // Timing
(* {0.000226, Null} *)

g1 == g2
(* True *)
POSTED BY: Rohit Namjoshi
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract