Efficiently determining the largest minimum cost to travel from a fixed source to an arbitrary sink in a weighted graph

Question

Let $v_i$ be a vertex in a graph $G$ with vertices $(v_1,...,v_N) \in V$ and edges $(e_1,...,e_M) \in E$ with associated weights $(w_1,...,w_M)$. Let $v_s \in V$ be specified vertex in the graph. In Mathematica 9, beyond repeatedly applying Dijkstra's algorithm by way of FindShortestPath[] and then summing the weights along the edges of each path, is there an efficient way to return the set of minimum costs to travel from $v_s$ to all other vertices $v_i \neq v_s$?

Also, other than finding the maximum value of this matrix, is there an efficient way to detect if one path exists where the minimum cost exceeds some threshold $T$?

Answer 1

You could use GraphDistance function to get distances from the given vertex to all others:

g = PolyhedronData["Dodecahedron", "SkeletonGraph"];
w = RandomInteger[{0, 10}, EdgeCount[g]];
wg = SetProperty[g, EdgeWeight -> w];

In[10]:= GraphDistance[wg, 1]
Out[10]= {0, 24., 14., 11., 21., 15., 10., 10., 7., 4., 14., 14., 
         21., 6., 3., 5., 11., 14., 18., 12.}

If you want to find the maximum value (the length of the longest shortest path), you can use VertexEccentricity function:

In[11]:= VertexEccentricity[wg, 1]
Out[11]= 24.

Answer 2

Algorithmic Graph Theory

I'll try to give you an answer for your first question. I'll use the Combinatorica package that ships with Mathematica.

Let's initialize a Dodecahedral Graph:

<< Combinatorica`
g = DodecahedralGraph

Now show the Euclidian shortest paths from vertex 1 to all other vertices in this dodecahedral graph, using ShortestPathSpanningTree:

t = ShortestPathSpanningTree[
SetEdgeWeights[g, WeightingFunction -> Euclidean], 1];

ShowGraphArray[{g, t}, VertexStyle -> Disk[0.05], VertexNumber -> True]

Side Note:

ShortestPathSpanningTree does internally call ChooseShortestPathAlgorithm to determine whether to use Dijkstra's algorithm or Bellman-Ford.

This decision is based on the presence of negative edge weights and the sparsity of the graph.

Side Note End

You could use Floyd-Warschall shortest path algorithm as well, using Combinatorica.

Let's start by generating random integer weights and compute the matrix of shortest-path distances between pairs or vertices:

g = SetEdgeWeights[CompleteGraph[7], 
    WeightingFunction -> RandomInteger, WeightRange -> {0, 10}];
    (s = AllPairsShortestPath[g]) // TableForm

0   1   3   1   3   4   3
1   0   2   0   2   4   3
3   2   0   2   0   2   1
1   0   2   0   2   4   3
3   2   0   2   0   2   1
4   4   2   4   2   0   3
3   3   1   3   1   3   0

Specifying the Parent tag produces parent information, in addition to the shortest-path distances. The (i,j)th entry in the parent matrix contains the predecessor of j in a shortest path from i to j:

First[AllPairsShortestPath[g, Parent]] // TableForm

0   1   3   1   3   4   3
1   0   2   0   2   4   3
3   2   0   2   0   2   1
1   0   2   0   2   4   3
3   2   0   2   0   2   1
4   4   2   4   2   0   3
3   3   1   3   1   3   0

How shorter does travel get if we take shortest path rather than direct hops?

(ToAdjacencyMatrix[g, EdgeWeight] - s) /. Infinity -> 0 // TableForm

0   7   4   0   0   0   0
7   0   7   0   0   4   0
4   7   0   5   0   7   0
0   0   5   0   7   2   6
0   0   0   7   0   0   7
0   4   7   2   0   0   6
0   0   0   6   7   6   0

I hope I've even touched what you're asking for.

P.S.: Since there is a new Graph functionality in Mathematica it is really confusing how to use them properly. I think it is time for a clean up for the next version of Mathematica.