QUESTION
(a) Write down the Update Step in the Dijkstra's algorithm explaining its complexity.
(b) Propose a Generic Algorithm for Depth-First Search Algorithm, assuming the Initialisation procedure has already been implemented.
(c) Below is the algorithm of a flow decomposition algorithm.
begin
Initialize
while y ≠Ø do
begin
Select(s, y)
Search(s, y)
if a cycle C is found then do
begin
let D = Capacity(C, y)
Add Flow(D, C) to cycle flows
Subtract Flow(D, C) from y.
end
if a path P is found then do
begin
let D = Capacity(P, y)
Add Flow(D, P) to path flows
Subtract Flow(D, P) from y.
end
end
Describe the complexity of the following:
i) Selecting the initial node,
ii) Finding a cycle or a path,
iii) Update step.
(c) Write down Dijkstra's Algorithm, clearly indicating the variables used.