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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Maybe you can construct the line graph of g to get a edge-weighted graph for FindShortestPath to work. $\endgroup$
    – Silvia
    Commented Nov 27, 2014 at 19:29
  • $\begingroup$ @Silvia Can you explain how to do it with Mathematica? You can post it as an answer. $\endgroup$
    – shrx
    Commented Nov 27, 2014 at 19:30
  • 3
    $\begingroup$ Define your edge weights as the sums of the corresponding pairs of vertex weights. $\endgroup$
    – Daniel Lichtblau
    Commented Nov 27, 2014 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
    Commented Nov 27, 2014 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
    Commented Nov 28, 2014 at 4:30

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Nov 28, 2014 at 14:12
  • $\begingroup$ In line 2 there is the misspelling 'VertextWeight'. $\endgroup$
    – David G. Stork
    Commented Dec 2, 2014 at 0:36

Your Answer

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

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