as i read the following text :
“Let P be a shortest path from some vertex s to some other vertex t in a graph. If the
weight of each edge in the graph is increased by one, P will still be a shortest path
from s to t”
Solution: False. the shortest path would change if 1 was added to every edge weight.
- easy to implement method to fit a power function (regression)
- What algorithm is used by computers to calculate logarithms?
- number of derangements
- Why does this algorithm to plot implicit equations work?
- Why does Strassen's algorithm work for $2\times 2$ matrices only when the number of multiplications is $7$?
- Calculation of Bessel Functions
I ran into a new question:
Suppose we have a Graph G in which weight of all edges is >1 (positive). If we increase weight of all edges by one, the shortest path between two specific vertex has the same edges.
I doubt about this question. would u please anyone clarify me?
Let $G$ be the complete graph on three vertices $A,B,$ and $C$. Let edges $AB$ and $BC$ have weight $2$, and edge $AC$ have weight $4.5$.
Then the shortest path from $A$ to $C$ is via $B$. But if you increase the weights to $3,3,$ and $5.5$, the shortest path is the edge $AC$.
If you want integer weights, you can do it with four points, with edge weights $AB=BC=CD=2$, $AD=7$.
A path with less edges has its weight increase less under the add-1-to-each-edge scenario than a path with more edges. So a path with initially higher weight could be surpassed by a lower weight path with more edges.