5
$\begingroup$

I have a weighted graph on which I want to perform some FindShortestPath calculations. However, the problem is that my weights are defined for vertices with VertexWeight, but FindShortestPath can only use edge weights defined with EdgeWeight. For example, if I have a simple grid graph

g = GridGraph[{2, 2}, VertexWeight -> {1, 2, 1, 1}, VertexLabels -> "VertexWeight"]

and I compute the shortest path between the lower left and the upper right corner

FindShortestPath[g, 1, 4]
{1, 2, 4}

it would give me the path over the upper left vertex which is not what I want, because this vertex has a bigger weight than the vertex in the opposite corner. How can I calculate the shortest path with regard to vertex weights?

$\endgroup$
  • 1
    $\begingroup$ Maybe you can construct the line graph of g to get a edge-weighted graph for FindShortestPath to work. $\endgroup$ – Silvia Nov 27 '14 at 19:29
  • $\begingroup$ @Silvia Can you explain how to do it with Mathematica? You can post it as an answer. $\endgroup$ – shrx Nov 27 '14 at 19:30
  • 3
    $\begingroup$ Define your edge weights as the sums of the corresponding pairs of vertex weights. $\endgroup$ – Daniel Lichtblau Nov 27 '14 at 20:18
  • 1
    $\begingroup$ @shrx: Assuming your start and end vertices are known in advance, you can fix Daniel's proposal by subtracting half the initial vertex weight from all edges emanating from it, and subtract half the end vertex weight from all edges emanating from it. That way, the first and last vertex weights aren't counted. $\endgroup$ – DumpsterDoofus Nov 27 '14 at 21:07
  • 2
    $\begingroup$ I do not see the issue. If you define edge weights by thatn summing, then every initial segment contains the initial vertex weight and so that part is a wash. Likewise for the terminating vertex weight and final segment. Another way to view it as this: every path will have weight equal to twice the weights of the intermediate vertices, plus the (constant) sum of the start and end weights. $\endgroup$ – Daniel Lichtblau Nov 28 '14 at 4:30
4
$\begingroup$

Starting from the graph indicated.

vertexWeight={1, 2, 1, 1};
g = GridGraph[{2, 2}, VertexWeight -> vertextWeight, 
  VertexLabels -> "VertexWeight"]
m = AdjacencyMatrix[g];
{l1, l2} = Dimensions[m];
h = WeightedAdjacencyGraph[
  Table[m[[i, j]] (vertexWeight[[i]] + vertexWeight[[j]]), {i, l1}, {j, 
     l2}] /. Rule[0, \[Infinity]], VertexLabels -> "Name", 
  EdgeLabels -> "EdgeWeight", GraphLayout -> "SpringEmbedding"]
sp=FindShortestPath[h, 1, 4]
(*{1, 3, 4}*)
HighlightGraph[h, PathGraph[FindShortestPath[h, 1, 4]], 
 GraphHighlightStyle -> "Dashed"]

Mathematica graphics

$\endgroup$
  • $\begingroup$ Thank you, with the illustration I can see now that @DanielLichtblau's suggestion will work even in those cases that looked problematic to me. I forgot to account that the vertex' weight would influence all edges connected to it. $\endgroup$ – shrx Nov 28 '14 at 14:12
  • $\begingroup$ In line 2 there is the misspelling 'VertextWeight'. $\endgroup$ – David G. Stork Dec 2 '14 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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