0
$\begingroup$

Given an undirected connected simple graph with distinct edge weights. If we add a constant value to each edge of graph then : single source shortest path of new graph can be changed?


My attempt :

If question was for MST(minimum spanning tree) then it was not changed. Can you explain for SSSP(single source shortest path)?

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $G$ be a triangle with vertices $x,y$, and $z$ and edge weights $1$ for $xy$, $2$ for $yz$, and $4$ for $xz$. Take $x$ as source. The shortest path from $x$ to $z$ in $G$ is $xyz$, with weight $3$, but if you add $2$ to each of the weights, the shortest path from $x$ to $z$ is $xz$, with weight $6$. The shortest path from $x$ to $y$ does not change: it is still $xy$.

$\endgroup$
1
  • $\begingroup$ @Mithlesh: You’re welcome. $\endgroup$ Feb 6, 2016 at 12:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .