Write down dijkstra''s algorithm, Basic Computer Science

Assignment Help:

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.


Related Discussions:- Write down dijkstra''s algorithm

Coaxial cables, Coaxial Cables: Another metallic transmission medium w...

Coaxial Cables: Another metallic transmission medium which offers a large bandwidth, is the coaxial cable. Such cables consist of an outer protective shell made of copper tube

Mr, Please what is the different between computer science and information t...

Please what is the different between computer science and information technology? Which of this require too much reading? Thanks

Unix shell and history problem, UNIX Shell and History feature. 1.Creating ...

UNIX Shell and History feature. 1.Creating a child process. 2.Creating a history feature. Its exactly "programming project 1 - Unix Shell and History Feature (p.157-159)" in the Si

Sequential-access memory device, Sequential-access memory device: A  S...

Sequential-access memory device: A  Sequential-access  memory device reads data in sequence. In other words, information on a serial device can only be retrieved in the same s

Vector processing, what are the chrateristics of vector processing

what are the chrateristics of vector processing

Turn-around, The term ‘page traffic’ describes

The term ‘page traffic’ describes

An e-mail account, An E-Mail Account: Inbox: Inbox is the main folder ...

An E-Mail Account: Inbox: Inbox is the main folder in your email account. It contains all the e-mails that have arrived in your e-mail account. You can click on inbox to see t

Differentiate Preemptive and Nonpreemptive Scheduling?, The Scheduling algo...

The Scheduling algorithms can be divided into two parts with respect to how they deal with clock interrupts. 1) Nonpreemptive Scheduling: A scheduling

What is a stateless and and a stateful server, StatefulServer, maintains so...

StatefulServer, maintains some information between requests. Requires smaller messages, since some information is kept between contacts, example: FTP, telnet. Stateless Server req

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd