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

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

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.