You are given a directed graph G(V,E) with a non-negative function f defined ove

Question

You are given a directed graph G(V,E) with a non-negative function f defined over E, and a non-negative function d defined over V. For each edge e in E, the value f(e) indicates the delay along the edge e. Similarly, for each vertex v in V, the value d(v) indicates the delay at vertex v. The functions f and d may be viewed as modeling link delays and router delays, respectively, in a communication network.

The goal of this problem is to solve a more general shortest paths problem that takes in to account both the link and the router delays. For any directed path P in the graph, the delay of the path P is defined to be the sum of the delays of the edges on the path P as well as the sum of the delays on the vertices that appear on the path P, including the first and last vertex in P. Design and analyze an O((V + E)logV) time algorithm that solves the single-source shortest paths problem in this more general setting. Assume that G is given in the adjacency list representation.

Explanation / Answer

algorithm

1. represent the graph in adjecency list representation

2. save the delay of each link and node (using maps will be convenient)

3.now create an array delay[] which stores delay from source node to each index of the array and initialise it to maximum value

also create an array visited[] and initialise to 0;

4.now get the source node , say, s delay[s] = (delay at node s)

5 now a create a priority queue pq which holds a pair of elements (delay[node],node)

6 now insert (delay[s],s) in priority queue.

7. while(pq is not empty)

do

pop node from the pq;

for(every node' in the adjacency list of the node )

do

if(visited[node'] == 0 and delay[node'] >delay[node] + delay in link node to node' + delay at node')

{

delay[node'] =delay[node] + delay in link node to node' + delay at node'

visited[node'] = 1;

push pair of delay[node'] and node' in pq;

}

end

end;

8 . after doing step 7 we wll get shortest delay path from source s to every node in the graph

time complexity is O((V + E)logV) because it is similar djikstra algorithm

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.