Let G be a directed graph where each edge e has a capacity c(e)>0 associated wit

Question

Let G be a directed graph where each edge e has a capacity c(e)>0 associated with it. That is, c(e) describes how much edge e can "carry". Let P=e1; e2; : : : ; ek be a path in G. The capacity of P is dened as the minimum edge capacity in P;

Let s be a node in G. Modify Dijkstra's algorithm to determine a maximum capacity path from s to every other node in the graph. That is,

Redefine D[v]. For this problem, what should D[v] denote?

What are the base cases for the D-values?

Should you use a max-heap or a min-heap?

How do you update the D-values?

Once you've answered the above questions, rewrite the pseudocode. What does this modied version of Dijkstra's algorithm work?

Explanation / Answer

function Dijkstra(Graph, source):
for each vertex v in Graph:                                 // Initializations
D[v] := -infinity ;                                // Unknown distance function from
// source to v
previous[v] := undefined ;                              // Previous node in optimal path
end for                                                     // from source
width[source] := infinity ;                                 //distance from source to source
Q := the set of all nodes in Graph ;                        // All nodes in the graph are
// unoptimized – thus are in Q
while Q is not empty:                                      // The main loop
u := vertex in Q with largest width in D[] ;       // Source node in first case
remove u from Q ;
if D[u] = -infinity:
break ;                                            // all remaining vertices are
end if                                                 // inaccessible from source
for each neighbor v of u:                              // where v has not yet been
// removed from Q.
alt := max(D[v], min(width[u], D_between(u, v))) ;
if alt > D[v]:                                 // Relax (u,v,a)
D[v] := alt ;
previous[v] := u ;
decrease-key v in Q;                           // Reorder v in the Queue
end if
end for
end while
return D;
endfunction

we need to use max heap for finding maximim capacity.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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