Dijkstra's Algorithm Single Source Shortest Path in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of Dijkstra's Algorithm?

To find the shortest path from a single starting point (source) to all other points (nodes) in a graph with non-negative edge weights.

intermediate

In Dijkstra's Algorithm, what data structure is commonly used to select the next node with the smallest distance?

A priority queue (often implemented as a min-heap) is used to efficiently pick the node with the smallest current distance.

intermediate

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

Because it assumes that once a node's shortest distance is found, it won't change. Negative edges can create shorter paths later, breaking this assumption.

advanced

What is the time complexity of Dijkstra's Algorithm using a min-heap and adjacency list?

O((V + E) log V), where V is the number of vertices and E is the number of edges.

intermediate

Explain the relaxation step in Dijkstra's Algorithm.

Relaxation means checking if the current known distance to a neighbor can be improved by going through the current node. If yes, update the neighbor's distance.

What type of graph edges does Dijkstra's Algorithm require?

A Only unweighted edges

B Non-negative edge weights

C Negative edge weights allowed

D Edges with zero weight only

Dijkstra's Algorithm works correctly only if all edge weights are zero or positive.

Which data structure helps efficiently pick the next closest node in Dijkstra's Algorithm?

A Stack

B Queue

C Priority Queue

D Linked List

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

What happens during the relaxation step?

A We update the shortest distance to neighbors if a shorter path is found

B We remove nodes from the graph

C We add new edges to the graph

D We reset all distances to infinity

Relaxation updates the shortest known distances to neighbors if a better path is found.

What is the initial distance to the source node in Dijkstra's Algorithm?

A Negative one

B Infinity

C One

D Zero

The source node distance is zero because the distance from the source to itself is zero.

Which of these is NOT true about Dijkstra's Algorithm?

A It works with negative edge weights

B It updates distances through relaxation

C It uses a priority queue for efficiency

D It finds shortest paths from one source to all nodes

Dijkstra's Algorithm does not work correctly with negative edge weights.

Describe the main steps of Dijkstra's Algorithm for finding shortest paths.

Think about how you keep track of shortest distances and update them.

Explain why Dijkstra's Algorithm cannot handle negative edge weights and what could happen if it tries.

Consider what happens if a shorter path appears after a node is finalized.