Graph basics I

Computer Science Level 2

Consider the following weighted directed graph:

Dijkstra algorithm is ran, starting at S S . What is the order in which vertices get removed from the priority queue?

Image credit: snipview
S,D,E,F,C,B,A S,D,E,C,F,A,B S,C,E,F,B,A,D S,C,A,D,F,E,B

View wiki
Thaddeus Abiy by Thaddeus Abiy , 25, Ethiopia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Christopher Boo
May 23, 2016

Actually it depends on how you implement Dijkstra's Algorithm. The priority queue might have duplicate numbers in my implementation but I assume just look at the first occurrence. 

1
2
3
4
5
6
7
8
 
S(0)                # push : D(2) E(3) F(6)    pop : S
D(2) E(3) F(6)      # push : C(5)              pop : D
E(3) C(5) F(6)      # push : B(9) C(4)         pop : E
C(4) C(5) F(6) B(9) # push : A(8)              pop : C
C(5) F(6) A(8) B(9) # push : -                 pop : C
F(6) A(8) B(9)      # push : -                 pop : F
A(8) B(9)           # push : -                 pop : A
B(9)                # push : -                 pop : B

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...