Shortest path in a graph with weighted edges and vertices I am considering a problem of route planning (from a source $s$ to sink $t$) in a undirected graph with weighted edges and vertices.
The goal is to find a shortest path between the source $s$ and the sink $t$. Intuitively, the path length is the sum of the weights of the edges and vertices of the paths (formally, let $k$ be the number of edges of a path: $\sum_{i=0}^k c(v_i) + \sum_{i=1}^k w(v_i−1, v_i)$).
A first idea that came to my mind, was to replace each vertex with a clique of $\delta(v)$ vertices (ie equal to his degree).
Each incident edge on the vertex will be assigned to only one of the vertices of the clique.
Each edge of the clique $C_{v_i}$ will be equal to cost $c(v_i)$. In this way it forces the algorithm to switch to force on an edge of the clique (simulating the payment of the cost of the vertex to which has been replaced).
Let $G'$ the graph resulted from this transformation, it runs on it Dijkstra's algorithm to find the shortest path from $s$ to $t$.
Unfortunately I was not able to prove it correct it the cost of construction of $G'$ (to be honest, I'm not even sure that this is a good idea).
Can any of you help me?
 A: Instead of replacing a node $v$ by a clique, replace it with an edge $(v_1,v_2)$ with weight $c(v)$, and link all neighbors of $v$ to $v_1$ and $v_2$.
A: For simplicity, I will assume that your graph is simple. Let $ w': E \rightarrow \mathbb{R} $ be new edge weights defined as:
$$
w'([u,v]) = w([u,v]) + \frac{c(u)}{2} + \frac{c(v)}{2} 
$$
Let $ \gamma = v_0 \rightarrow v_1 \rightarrow \cdots \rightarrow v_n $ a path on the graph. The length of the path as you defined it is:
\begin{align*}
l(\gamma) &= \sum_{k = 0}^{n} c(v_k) + \sum_{k=0}^{n-1} w([v_k,v_{k+1}]) \\
&= \sum_{k=0}^{n} \frac{1}{2}c(v_k) + \sum_{k=0}^{n} \frac{1}{2}c(v_k) + \sum_{k=0}^{n-1} w([v_k,v_{k+1}]) \\
&= \left( \frac{1}{2}c(v_n)+\sum_{k=0}^{n-1} \frac{1}{2}c(v_k) \right) + \left(\frac{1}{2}c(v_0)+ \sum_{k=0}^{n-1} \frac{1}{2}c(v_{k+1})\right) + \sum_{k=0}^{n-1} w([v_k,v_{k+1}]) \\
&= \frac{1}{2} c(v_0) + \frac{1}{2} c(v_n) + \sum_{k=0}^{n-1} \left( w([v_k,v_{k+1}]) + \frac{1}{2}c(v_{k})+ \frac{1}{2}c(v_{k+1}) \right) \\
&= \frac{1}{2} c(v_0) + \frac{1}{2} c(v_n) + \sum_{k=0}^{n-1} w'([v_k,v_{k+1} ])
\end{align*}
So, it is the length of the path with just edge weights $ w' $ plus boundary terms that won't matter since you are fixing end points anyway.
