157. OCR A Level (H446) SLR26 – 2.3 Dijkstra’s shortest path

What is the main purpose of Dijkstra's shortest path algorithm?

• To perform a depth-first search on a graph

• To identify negative weight cycles in a graph

• To calculate the total weight of a graph

• To find the shortest path between one node and all other nodes on a weighted graph

Answer explanation

Dijkstra's algorithm is used to find the shortest path between one node and all other nodes on a weighted graph.

Which algorithm is considered a special case of the A* algorithm with no heuristics?

• Depth-first search

• Dijkstra's shortest path algorithm

• Breadth-first search

• Bellman-Ford algorithm

Answer explanation

Dijkstra's shortest path algorithm is considered a special case of the A* algorithm with no heuristics.

What is a limitation of Dijkstra's shortest path algorithm?

• It cannot find the shortest path in unweighted graphs

• It doesn't work for edges with a negative weight value

• It requires the graph to be acyclic

• It can only find the shortest path to adjacent nodes

Answer explanation

Dijkstra's algorithm cannot handle negative edge weights, making it unsuitable for graphs with negative weight values.

For what problem did Dijkstra develop his algorithm?

• To find the shortest route of travel between Rotterdam and Groningen

• To improve efficiency in sorting algorithms

• To optimize database search queries

• To solve the traveling salesman problem

Answer explanation

Dijkstra developed his algorithm to find the shortest route of travel between Rotterdam and Groningen.

Which data structure can be used to implement Dijkstra's shortest path algorithm?

• Table or array

• Queue

• Stack

• Binary tree

Answer explanation

Table or array is the correct choice as it allows for efficient storage and retrieval of distances in Dijkstra's algorithm.

What initial value is set for each node's distance from the start in Dijkstra's algorithm?

• Zero

• The weight of the edge connecting it to the start node

• Infinity

• One

Answer explanation

In Dijkstra's algorithm, each node's distance from the start is initially set to Infinity until it is updated during the algorithm execution.

What does the algorithm do when it finds a shorter path to a node?

• It restarts the algorithm from the current node

• It discards the new path as irrelevant

• It updates the node's distance and marks it as visited

• It updates the node's distance from the start to the newly calculated distance

Answer explanation

When the algorithm finds a shorter path to a node, it updates the node's distance from the start to the newly calculated distance.

How does Dijkstra's algorithm proceed after marking a node as visited?

• It considers all nodes again

• It backtracks to the start node

• It terminates immediately

• It finds the node with the shortest distance from the start that has not yet been visited

Answer explanation

After marking a node as visited, Dijkstra's algorithm finds the node with the shortest distance from the start that has not yet been visited.

What is the result of Dijkstra's algorithm?

• The total weight of the graph

• A list of all nodes in the order they were visited

• The shortest path from the start node to a specified goal node

• The maximum distance between any two nodes

Answer explanation

Dijkstra's algorithm results in the shortest path from the start node to a specified goal node.

What is a practical application of Dijkstra's shortest path algorithm?

• Generating random numbers

• Encrypting data

• Sorting a list of numbers

• GPS navigation

Answer explanation

Dijkstra's shortest path algorithm is commonly used in GPS navigation systems to find the most efficient route between two points, making it the practical application in this context.