Why I cannot calculate all edge weights beforehand:
I have many large graphs for which I'd like to find the shortest path between two vertices (
EdgeWeight between two vertices is a function of the two, requiring a
URLFetch and therefore takes some (significant ~1s) time to run, which motivates the following.
My desire is to be able to specify a function for
EdgeWeight, along the lines of
EdgeWeight -> MyFunction[#1, #2]
with the ultimate goal of speeding up the shortest path finding process.
First a preliminary question:
By that I mean, will it search exhaustively, or will it stop when no remaining unsearched paths could possibly be shorter? (This obviously requires positive edge weights, as is the case I am considering).
For example in the graphs below, in the first case the shortest route from the green vertex to the red is around the outside, and if we were using a function to calculate the edge weights we would likely need to evaluate it for most edges. However in the second case the increased cost of the 'spokes' means we should never need to evaluate to the weights around the outer rim.
I have tried to observe a timing difference in
FindShortestPath by extending the above demonstration to graphs with 50 rings and 20 vertices per ring, and comparing the timing for the case where the shortest path is to go around the outside, to the case where the innermost spokes are prohibitively expensive and the shortest route is the inner ring.
However, I see no timing differences.
Is my (big) graph too small, or is the solver exhaustive?
Hopefully the appeal of an edge weight function is now clear. If the solver is intelligent then I wouldn't have to evaluate all the edge costs at the outset, which is time consuming, but rather those that are potentially of interest would be generated by the solver as required. (Also I think an
EdgeWeightFunction would be elegant).
Hopefully you guys can as ever point out the flaw in my thoughts!