Dijkstra's Algorithm Single Source Shortest Path in DSA C - 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 (vertices) in a graph with non-negative edge weights.

intermediate

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

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

intermediate

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

Because it assumes that once a vertex'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.

beginner

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 vertex. If yes, update the neighbor's distance.

What type of graph edge weights does Dijkstra's Algorithm require?

A Any weights including negative cycles

B Negative weights allowed

C Only zero weights

D Non-negative weights

Dijkstra's Algorithm only works correctly with non-negative edge weights.

Which data structure helps efficiently pick the next vertex with the smallest distance in Dijkstra's Algorithm?

A Priority queue (min-heap)

B Stack

C Queue

D Linked list

A priority queue (min-heap) is used to select the vertex with the smallest tentative distance efficiently.

What happens during the relaxation step in Dijkstra's Algorithm?

A Edges are reversed

B Distances to neighbors are updated if a shorter path is found

C Vertices are removed from the graph

D All distances are reset to infinity

Relaxation updates the distance to neighbors if a shorter path through the current vertex is found.

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

A Infinity

B Negative infinity

C Zero

D One

The source vertex distance is set to zero because the distance from the source to itself is zero.

What is the worst-case time complexity of Dijkstra's Algorithm using a simple array instead of a priority queue?

A O(V^2)

B O(E log V)

C O(V + E)

D O(log V)

Using a simple array to find the minimum distance vertex leads to O(V^2) time complexity.

Describe the main steps of Dijkstra's Algorithm for finding the shortest path from a source vertex.

Think about how distances are updated and how the next vertex is chosen.

Explain why Dijkstra's Algorithm does not work with graphs containing negative edge weights.

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