In: Computer Science
Let G = (V, E) be a directed acyclic graph modeling a communication network. Each link e in E is associated with two parameters, w(e) and d(e), where w(e) is a non-negative number representing the cost of sending a unit-sized packet through e, and d(e) is an integer between 1 and D representing the time (or delay) needed for transmitting a packet through e. Design an algorithm to find a route for sending a packet between a given pair of nodes in G such that the total delay is no more than k and the total cost is minimized. Your algorithm should run in O(k(|E| + |V |)) time and O(k|V |) space (additional to space for storing the graph). Hint: It is possible to use a linear time (i.e., O(n + m) time) algorithm called topological sort to compute the shortest path between any pair of vertices in a unit-weighted (i.e., all edges have weight 1) graph with n vertices and m edges.
Actually the question is this much only. I have been given HW and this question has been asked. I am unable to understand this that is why I posted here.
Summary of question:
According to question you will be given an acyclic graph (can be treated as directed tree) because no cylcles will be there in the graph.
After that for each edge in that graph you will be given 2 values ( w, d ) where "w" will tell you the cost it takes to move from one vertex to another vertex and "d" will tell you the time it take.
So, you have to comeup with an algorithm that can minimize the cost of sending the packet from one point to another and time taken should be less than "k".
Algorithm:
Algorithm:
We will find the cost it will take to reach from source to destination in minimum time
Store this answer in a variable say min_cost
Now we will find the cost it will take if time taken is 1 more than the minimum time, using BFS
Find minimum of previous(min_cost) and now calculated cost
And increment the time by 1
Repeate until time becomes greater than "k"
The cost we will get, will be the minimum cost
Time complexity will be O( k * (|V|+|E| ) ) in worst case
Space complexity will be O( |V| ) because BFS use queue to store values