4
$\begingroup$

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$?

$\endgroup$

2 Answers 2

4
$\begingroup$

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.
$\endgroup$
6
$\begingroup$

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]

enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.