FindShortestPath with VertexWeight - Mathematica Stack Exchange most recent 30 from mathematica.stackexchange.com 2019-09-23T10:41:22Z https://mathematica.stackexchange.com/feeds/question/66760 https://creativecommons.org/licenses/by-sa/4.0/rdf https://mathematica.stackexchange.com/q/66760 5 FindShortestPath with VertexWeight shrx https://mathematica.stackexchange.com/users/6849 2014-11-27T19:11:58Z 2014-11-28T13:40:44Z <p>I have a weighted graph on which I want to perform some <code>FindShortestPath</code> calculations. However, the problem is that my weights are defined for vertices with <code>VertexWeight</code>, but <code>FindShortestPath</code> can only use edge weights defined with <code>EdgeWeight</code>. For example, if I have a simple grid graph</p> <pre><code>g = GridGraph[{2, 2}, VertexWeight -&gt; {1, 2, 1, 1}, VertexLabels -&gt; "VertexWeight"] </code></pre> <p>and I compute the shortest path between the lower left and the upper right corner</p> <pre><code>FindShortestPath[g, 1, 4] </code></pre> <blockquote> <pre><code>{1, 2, 4} </code></pre> </blockquote> <p>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?</p> https://mathematica.stackexchange.com/questions/66760/-/66806#66806 4 Answer by Zviovich for FindShortestPath with VertexWeight Zviovich https://mathematica.stackexchange.com/users/1096 2014-11-28T13:40:44Z 2014-11-28T13:40:44Z <p>Starting from the graph indicated.</p> <pre><code>vertexWeight={1, 2, 1, 1}; g = GridGraph[{2, 2}, VertexWeight -&gt; vertextWeight, VertexLabels -&gt; "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 -&gt; "Name", EdgeLabels -&gt; "EdgeWeight", GraphLayout -&gt; "SpringEmbedding"] sp=FindShortestPath[h, 1, 4] (*{1, 3, 4}*) HighlightGraph[h, PathGraph[FindShortestPath[h, 1, 4]], GraphHighlightStyle -&gt; "Dashed"] </code></pre> <p><img src="https://i.stack.imgur.com/iq6mR.png" alt="Mathematica graphics"></p>