Preview

02 - Dijkstra's shortest path algorithm

 1. Dijkstra was a real person. He has been quoted saying: "_____________________ is prerequisite for reliability"
edsger_theman_himself.png

  simplicity

  englightenment

  complexity

  speed

 2. Dijkstra's algorithm is an algorithm for finding the shortest paths between _______ in a graph, which may represent, for example, road network

  nodes

  edges

  data points

  fields

 3. Dijkstra's algorithm initially marks the distance (from the starting point) to every other intersection on the map with _________________

  zero

  a single '1'

  NULL

  infinity

 4. Below is a graph representation of the places that the travelling salesman visits. Using this graph, what would Dijkstra's algorithm find to be the shortest path from place A to place F?
travelling_sales_man_graph.png

  A - D - F

  A - C - F

  A - F

  A - B - F

 5. Using Dijkstra's algorithm to find the shortest path from A to F, the first thing you might do is:

  Mark F as the last node

  Mark B as the first node to check with a distance of 5

  Mark C as the current node to begin with

  Mark A as the current node

 6. In the above example, once A has been visited, what would come next, if following Dijkstra's algorithm?

  Noting that D would be the shortest distance from A

  Marking D as the next current node

  Noting that C is the shortest distance from A

  Noting that F would be the next node to visit

 7. The following excerpt explains one of the steps in Dijkstra's algorithm. Can you fill in the blanks? 
From the current intersection, 
update the distance to every unvisited 
intersection that is directly connected to it. 

This is done by determining the sum of the 
distance between an unvisited intersection 
and the value of the current intersection,
 and relabeling the unvisited intersection
 with this value (the sum), 
if it is ______ than its current value

  more

  higher

  equal to or more than

  less

 8. For the following example, read the excerpt below and fill in the blanks. 
Now, we check the neighbours of our current
 node (A, B and D) in no specific order. 

Let's begin with B. We add the minimum
distance of the current node (in this case, 0)
 with the weight of the edge that connects 
our current node with B,


and we obtain _______________________
graph_dijkstras_problem_1.png

  7 + infinty = infinity

  7 + 1 = 8

  7 + 3 = 10

  0 + 7 = 7

 9. When you are selecting a new 'current node', that node must be the ___________ node with the _________ minimum distance

  visited/ largest

  unvisited/ smallest

  unvisited / largest

  visited / smallest

 10. Fill in the blanks for this part of the algorithm (that is part of dijkstra's algorithm) 
For each neighbour N of your current node C: 
add the current distance of C with the weight
of the edge connecting C-N. If it's _________
than the current distance of N, set it
as the new current distance of N

  equal to or greater

  lengthier

  bigger

  smaller


Report an error