1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Perhaps a better way might be to change the weight of each edge $ (u,v) $ as $ w' ( (u,v) ) = w(u,v) + c(u)/2 + c(v)/2 $. I think the vertex+edge weight of any path is equivalent to the weight of just edges with $ w' $. $\endgroup$
    – user226970
    May 18, 2016 at 0:15
  • $\begingroup$ At the moment, your idea seems good, but I would find a way to prove it formally. $\endgroup$
    – Fabrizio Lo Verde
    May 19, 2016 at 23:39

2 Answers 2

Reset to default
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I thank you, you were very clear and precise. $\endgroup$
    – Fabrizio Lo Verde
    May 20, 2016 at 14:14
  • $\begingroup$ I am happy I could help! $\endgroup$
    – user226970
    May 20, 2016 at 23:20
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ If I understand your idea, unfortunately I already thought of us and found us some defect. Essentially the problem is that when I duplicate a vertex $v$ in $v_1$ and $v_2$ with the edge $(v_1, v_2)$ are not forced to cross it. For example: (lacking the weights on the edges, but the concept is the same). $\endgroup$
    – Fabrizio Lo Verde
    May 19, 2016 at 22:57

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.