Generalized shortest-paths problem. In Internet routing, there are delays on lin
ID: 3528744 • Letter: G
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.
Explanation / Answer
A simple modification in dijkstra algo will solve the question:
1 function ModifiedDijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity ; // Unknown distance function from
4 // source to v
5 previous[v] := undefined ; // Previous node in optimal path
6 end for // from source
7
8 dist[source] := cost[source] ; // Distance from source to source
9 Q := the set of all nodes in Graph ; // All nodes in the graph are
10 // unoptimized - thus are in Q
11 while Q is not empty: // The main loop
12 u := vertex in Q with smallest distance in dist[] ; // Start node in first case
13 remove u from Q ;
14 if dist[u] = infinity:
15 break ; // all remaining vertices are
16 end if // inaccessible from source
17
18 for each neighbor v of u: // where v has not yet been
19 // removed from Q.
20 alt := dist[u] + dist_between(u, v) +cost[v];
21 if alt < dist[v]: // Relax (u,v,a)
22 dist[v] := alt ;
23 previous[v] := u ;
24 decrease-key v in Q; // Reorder v in the Queue
25 end if
26 end for
27 end while
28 return dist;
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.