Generalized shortest-paths problem. In Internet routing, there are delays on lin
ID: 3829515 • Letter: G
Question
Generalized shortest-paths problem. In Internet routing, there are delays on lines but also, more significantly, delays at routers. This motivates a generalized shortest-paths problem. Suppose that in addition to having edge lengths {l_e: e E}, a graph also has vertex costs {c_upsilon: upsilon V}. Now define the cost of a path to be the sum of its edge lengths, plus the costs of all vertices on the path (including the endpoints). Give an efficient algorithm for the following problem. Input: A directed graph G = (V, E); positive edge lengths l_e and positive vertex costs c_upsilon; a starting vertex s V. Output: An array cost[] such that for every vertex u, cost[u] is the least cost of any path from s to u (i.e., the cost of the cheapest path), under the definition above. Notice that cost[s] = c_s.Explanation / Answer
The edge lengths are given by the length of the each edge and the cost of it end point given as,
l'(u,v) =l(u,v) +c(v)
To find the generalised paths we should find the shortest paths with modified edges weights we use dijkstra's algorithm ,
for all(u,v) E
l’(u, v) = l(u, v) + c(v)
end for
dist[·] = dijkstra(G,l',s) // dist[.] stores distances to all vertices in Graph
for all u E // The distance value is increased by c(s)
cost[u] = dist[u] + c(s) // c(s) is added to all the paths
end for
The running time of this algorithm is O((|V|+|E|)log(|V|)) .
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.