Preview

17 - Dijkstra's Algorithm

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

  complexity

  simplicity

  englightenment

  speed

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

  fields

  edges

  nodes

  data points

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

  zero

  infinity

  a single '1'

  NULL

 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 - B - F

  A - C - F

  A - F

  A - D - 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 A as the current node

  Mark C as the current node to begin with

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

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

  Noting that C is the shortest distance from A

  Noting that F would be the next node to visit

  Noting that D would be the shortest distance from A

  Marking D as the next current node

 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

  less

  equal to or more than

  higher

  more

 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 + 1 = 8

  0 + 7 = 7

  7 + 3 = 10

  7 + infinty = infinity

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

  visited / smallest

  visited/ largest

  unvisited/ smallest

  unvisited / largest

 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

  lengthier

  bigger

  smaller

  equal to or greater