Dijkstra's algorithm in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of Dijkstra's algorithm?

Dijkstra's algorithm finds the shortest path from a starting point to all other points in a graph with non-negative edge weights.

beginner

What type of graphs can Dijkstra's algorithm be applied to?

It works on graphs with non-negative edge weights, whether directed or undirected.

intermediate

How does Dijkstra's algorithm decide which node to visit next?

It always picks the unvisited node with the smallest known distance from the start.

intermediate

What data structure is commonly used to efficiently select the next node in Dijkstra's algorithm?

A priority queue (or min-heap) is used to quickly find the node with the smallest distance.

advanced

Why can't Dijkstra's algorithm handle graphs with negative edge weights?

Because it assumes once a node's shortest distance is found, it won't get shorter. Negative edges can break this assumption.

What does Dijkstra's algorithm compute?

A Detect cycles in a graph

B Minimum spanning tree

C Maximum flow in a network

D Shortest paths from one node to all others

Dijkstra's algorithm finds the shortest paths from a single starting node to all other nodes.

Which data structure helps Dijkstra's algorithm pick the next node efficiently?

A Stack

B Queue

C Priority queue

D Linked list

A priority queue allows quick access to the node with the smallest current distance.

Dijkstra's algorithm cannot be used if the graph has:

A Negative edge weights

B Multiple nodes

C Directed edges

D Loops

Negative edge weights can cause incorrect shortest path calculations in Dijkstra's algorithm.

What is the initial distance assigned to the starting node in Dijkstra's algorithm?

A Infinity

B Zero

C One

D Undefined

The starting node's distance to itself is zero.

When does Dijkstra's algorithm stop?

A When all nodes have been visited

B After visiting half the nodes

C When the shortest path to one node is found

D After a fixed number of steps

The algorithm finishes when it has found the shortest paths to all nodes.

Explain how Dijkstra's algorithm finds the shortest path in a graph.

Think about how the algorithm updates distances and chooses nodes step by step.

Describe why Dijkstra's algorithm does not work with negative edge weights.

Consider what happens if a path gets shorter after a node is processed.