Use the following directed graph.

A: to B is 4 & to F is 2

B: to A is 1 & C is 3 & to D is 4

C: to A is 6 & to B is 3 & to D is 7

D: to A is 6 & to E is 2

E: to D is 5

F: to D is 2 & to E is 3

a) Do Dijkstra's shortest path algorithm starting with C ending with E. Trace the algorithm using the same format as I use. Replace ?s and give the table per step.

Initially:

Tree has: C

Fringe (F*) has: A6, B3 and D7

DistTo of these are initialized to be the edge weights from C.

__________________________

DistTo CandidateEdge

T* C 0 start

F* A 6 from C

F* B 3 from C

F* D 7 from C

E inf

F inf

________________________

Step1:

Pick B (show that B is T* in the table)

B is next to A1, C3, D4.

Note that C is already *T.

Note that A and D are already in Fringe. Should we update them?

DistTo to these vertices when going through B:

DistTO[A] = DistTo[B] + 1 = 4 update (it is better)

DistTO[D] = DistTo[B] + 4 = 7 no change (it is not better)

DistTo CandidateEdge

T* C 0 start

F* A 4 from B updated

T* B 3 from C

F* D 7 from C unchanged

E inf

F inf

Step 2:

Pick A (show that it is T* in the table)

A is next to: F, B (show that they are F* if not already)(ignore if already *T)

DistTo to these Fringe (F*) vertices when going through A:

DistTO[F] = DistTO[A] + weight(A,F) = 6 update

(Update the table and indicate new or updated or unchaged in the table)

___________________________________

DistTo CandidateEdge

T* C 0 start

T* A 4 from B updated

T* B 3 from C

F* D 7 from C unchanged

E inf

F* F 6 from A new

________________________________________

Step 3:

Pick F (show that it is T* in the table)

F is next to: E,D. D is in the fringe (show that they are F* if not already)(ignore if already *T)

DistTo to these Fringe (F*) vertices when going through F:

DistTO[E] = DistTO[F] + weight(F,E) = 9 update

(Update the table and indicate new or updated or unchaged in the table)

_______________________________

DistTo CandidateEdge

T* C 0 start

T* A 4 from B

T* B 3 from C

F* D 7 from C

F* E 9 from F new

T* F 6 from A updated

____________________________________

Step 4:

Pick ?? (show that it is T* in the table)

?? is next to: ??? (show that they are F* if not already) (ignore if already *T)

DistTo to these Fringe (F*) vertices when going through ??:

DistTO[D] = DistTO[C] + weight(C,D) = 9 no change

(This is the updated table)

____________________________

DistTo CandidateEdge

T* C 0 start

T* A 4 from B

T* B 3 from C

T* D 7 from C

F* E 9 from F new

T* F 6 from A updated

______________________________________

Step 5:

Pick ?? (show that it is T* in the table)

?? is next to: ??? (show that they are F* if not already) (ignore if already *T)

DistTo to these Fringe (F*) vertices when going through ??:

DistTO[??] = DistTO[???] + ??? = ????

(This is the upadated table)

DistTo CandidateEdge

T* C 0 start

T* A 4 from B

T* B 3 from C

T* D 7 from C

T* E 9 from F updated

F* F 6 from A

Stop as soon E becomes *T.