G = (V,E) is a directed graph. For each vertex u E V, there is a price associate

Question

G = (V,E) is a directed graph. For each vertex u E V, there is a price associated with it Po. Define the coet array as follows. For each vEV, cost[w] = price of the cheapest node reachable frorn u(including u itself) Design an algorithm which fills the entire cost array(for all vertices) 1. Give a linear time algorithm that works on directed acyclic graphs 2. Extend this to linear time algorithm that works on all directed graphs. (Hint: Recall I directed graphs. (Hint: Recal the "two-tiered" structure of directed graphs)

Explanation / Answer

Algorithm for acyclic graphs:

void fillCost(graph G,int cost[])

{
for(i=0;i<v.size;i++)
{
  
if(cost[v[i]]==0)// check if cost of v[i] is already calculated or not
cost[v[i]] = aux_fill_cost(G,cost,v[i])// start from vertex 0 , this fuction will fill all its
}
}

int aux_fill_cost(graph G, int cost[], vertex v)

{

if(adj(v) == )// if the vertex has no adjecent node then return its price as cost[v]
return v.price;

int result = v.price;//inititalise result(cost of v) to v.price

for each u adj(v)
{
if(cost[u]==0)// check if cost of u is already calculated
  
{
cost[u] = aux_fill_cost(G,cost,u);
}
result = minimum(result,cost[u]);
}

return result;

}

Since each node is visted only once it will be executed in linear time

Algorithm for all graphs:

Step 1:

decompose the directed graph into its strongly connected components (it can be done in linear time)

Step 2:

for each strongly connected component C do the following

1) find minimum price of all vertices C and, let it be min

for each vertex v C:

v.price = min

The above things can be done in linear time as we are cvisiting each node atmost once

Step 3:

now consider each strongly connected component as a node , and its price = price of any vertex in that component

Now the problem is reduced to directed acyclic graph

solve it using first algorithm

Step 4:

for each strongly connected component C in G , do the following

for each vertex v C:

   cost[v] = cost[c] found in step 3

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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