Question

Generalized shortest-paths problem. In Internet routing, there are delays on lines but also, more signicantly, delays at routers. This motivates a generalized shortest-paths problem. Suppose that in addition to having edge lengths fle : e 2 Eg, a graph also has vertex costs fcv : v 2 V g. Now dene 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 efcient algorithm for the following problem. Input: A directed graph G = (V;E); positive edge lengths le and positive vertex costs cv; a starting vertex s 2 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 denition above. Notice that cost[s] = cs.

Answer 1

Algorithm:

1. Initialize cost[u] = ∞ for all u in V.

2. Set cost[s] = cs.

3. For each vertex v in V:

  a. Set dist[v] = 0.

  b. For each edge (u, v) in E:

     i. Set dist[v] = min(dist[v], cost[u] + le).

  c. Set cost[v] = min(cost[v], dist[v] + cv).

4. Return cost[].

Time complexity: O(VE)

What is time complexity?

The duration of the input determines how long it takes an algorithm to run, which is known as temporal complexity. It calculates how long it takes for each algorithm's code statement to run. It won't look at an algorithm's overall execution time. Instead, it is going to supply information about the variance (up or down) in execution time whenever the number of tests (significantly reduce) in an algorithms.

To know more about time complexity
https://brainly.com/question/18041135
#SPJ4