'verifying that node values are the shortes path to sink
A directed graph G with weighted edges with each node having a value d(v)
There is a sink node t. How do I determine if this d(v) = which is the length of the
shortest path from v to t? Is it possible to verify that using some way?
One complex way would be to use the Dijkstra variation to find the d(v) for each node v
and then see if it matches the given d(v), but this would take quadratic time
I am looking for some linear time algorithm to verify this
My Thoughts:
For each directed edge e from vertex v1 to v2 verify
d(v1) <=d(v2)+cost(e)
At least this condition should hold if the d(v) is the shortest
path to the sink not sure if this is enough or how to go about proving
it
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|