Dijkstra's Algorithm Single Source Shortest Path in DSA Python - Execution Trace

Concept Flow - Dijkstra's Algorithm Single Source Shortest Path

Start with source node

↓

Initialize distances: source=0, others=∞

↓

Create priority queue with source

↓

While queue not empty

↓

Extract node with smallest distance

↓

For each neighbor

↓

Calculate new distance

↓

If new distance < known distance

Yes↓

Update distance and add neighbor to queue

No↓

Repeat until queue empty

↓

Distances finalized

Dijkstra's algorithm finds shortest paths from one node to all others by repeatedly choosing the closest unvisited node and updating neighbors.

Execution Sample

DSA Python

graph = {
  'A': {'B': 1, 'C': 4},
  'B': {'C': 2, 'D': 5},
  'C': {'D': 1},
  'D': {}
}

# Find shortest paths from 'A'

This code finds shortest paths from node 'A' in a weighted graph using Dijkstra's algorithm.

Execution Table

Step	Operation	Current Node	Distances	Priority Queue	Visual State
0	Initialize distances and queue	None	{"A": 0, "B": ∞, "C": ∞, "D": ∞}	[('A', 0)]	A(0) B(∞) C(∞) D(∞)
1	Extract node with smallest distance	A	{"A": 0, "B": ∞, "C": ∞, "D": ∞}	[]	A(0) B(∞) C(∞) D(∞)
2	Update neighbors of A	A	{"A": 0, "B": 1, "C": 4, "D": ∞}	[('B', 1), ('C', 4)]	A(0) B(1) C(4) D(∞)
3	Extract node with smallest distance	B	{"A": 0, "B": 1, "C": 4, "D": ∞}	[('C', 4)]	A(0) B(1) C(4) D(∞)
4	Update neighbors of B	B	{"A": 0, "B": 1, "C": 3, "D": 6}	[('C', 3), ('D', 6)]	A(0) B(1) C(3) D(6)
5	Extract node with smallest distance	C	{"A": 0, "B": 1, "C": 3, "D": 6}	[('D', 6)]	A(0) B(1) C(3) D(6)
6	Update neighbors of C	C	{"A": 0, "B": 1, "C": 3, "D": 4}	[('D', 4), ('D', 6)]	A(0) B(1) C(3) D(4)
7	Extract node with smallest distance	D	{"A": 0, "B": 1, "C": 3, "D": 4}	[('D', 6)]	A(0) B(1) C(3) D(4)
8	No neighbors to update	D	{"A": 0, "B": 1, "C": 3, "D": 4}	[('D', 6)]	A(0) B(1) C(3) D(4)
9	Extract node with smallest distance	D	{"A": 0, "B": 1, "C": 3, "D": 4}	[]	A(0) B(1) C(3) D(4)
10	No neighbors to update	D	{"A": 0, "B": 1, "C": 3, "D": 4}	[]	A(0) B(1) C(3) D(4)

💡 Priority queue empty, all shortest distances finalized

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	Final
Distances	{"A": 0, "B": ∞, "C": ∞, "D": ∞}	{"A": 0, "B": 1, "C": 4, "D": ∞}	{"A": 0, "B": 1, "C": 3, "D": 6}	{"A": 0, "B": 1, "C": 3, "D": 4}	{"A": 0, "B": 1, "C": 3, "D": 4}
Priority Queue	[('A', 0)]	[('B', 1), ('C', 4)]	[('C', 3), ('D', 6)]	[('D', 4), ('D', 6)]	[]
Current Node	None	A	B	C	D

Key Moments - 3 Insights

Why do we add the same node 'D' twice to the priority queue with different distances?

Because when we find a shorter path to 'D' (distance 4), we add it again. The queue may have old entries (distance 6) which will be ignored when extracted since the distance is not better. See steps 6 and 7 in execution_table.

Why do we initialize distances to infinity except the source?

Infinity means we don't know any path yet. The source distance is zero because it's the start. This is shown in step 0 of execution_table.

Why do we stop when the priority queue is empty?

Because all nodes reachable have been processed with shortest distances. No more nodes to explore. This is the exit condition at step 10.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the distance to node 'C'?

A 4

B ∞

C 3

D 1

💡 Hint

Check the 'Distances' column at step 4 in execution_table.

At which step does the distance to node 'D' first get updated to 4?

A Step 6

B Step 2

C Step 4

D Step 8

💡 Hint

Look at the 'Distances' column and 'Operation' at steps 4 and 6.

If the edge from 'B' to 'D' had weight 1 instead of 5, how would the distance to 'D' change after step 4?

A Distance to 'D' would remain 6

B Distance to 'D' would be 2

C Distance to 'D' would be 4

D Distance to 'D' would be ∞

💡 Hint

Calculate new distance from 'A' to 'D' via 'B' with updated edge weight.

Concept Snapshot

Dijkstra's Algorithm:
- Start with source node distance 0, others ∞
- Use priority queue to pick closest unvisited node
- Update neighbors if shorter path found
- Repeat until all nodes processed
- Result: shortest distances from source to all nodes

Full Transcript

Dijkstra's algorithm finds the shortest path from one starting node to all other nodes in a weighted graph. It begins by setting the distance to the start node as zero and all others as infinity, meaning unknown. A priority queue keeps track of nodes to visit next, always choosing the closest unvisited node. For each chosen node, the algorithm checks its neighbors and updates their distances if a shorter path is found. Sometimes, the same node is added multiple times with different distances; only the shortest is used. The process continues until the priority queue is empty, meaning all shortest paths are found. The final distances show the minimum cost to reach each node from the start.

Practice

1. What is the main purpose of Dijkstra's Algorithm in graph theory?

easy

A. To sort vertices in topological order

B. To find the maximum flow in a network

C. To detect cycles in a graph

D. To find the shortest path from a single source to all other vertices

Solution

1. Step 1: Understand the algorithm's goal

   Dijkstra's Algorithm is designed to find the shortest distance from one starting point (source) to every other point in a graph.

2. Step 2: Compare with other graph algorithms

   Other algorithms like max flow or cycle detection serve different purposes, so they do not match Dijkstra's goal.

3. Final Answer:

   To find the shortest path from a single source to all other vertices -> Option D

4. Quick Check:

   Shortest path = find minimum distances [OK]

Hint: Dijkstra finds shortest paths from one start point [OK]

Common Mistakes:

• Confusing with max flow algorithms
• Thinking it detects cycles
• Assuming it sorts vertices

2. Which Python data structure is commonly used to efficiently select the next vertex with the smallest tentative distance in Dijkstra's Algorithm?

easy

A. List

B. Heap (Priority Queue)

C. Queue

D. Set

Solution

1. Step 1: Identify the need for efficient minimum extraction

   Dijkstra's Algorithm repeatedly picks the vertex with the smallest tentative distance, so an efficient way to get the minimum is needed.

2. Step 2: Choose the right data structure

   A heap or priority queue allows quick extraction of the smallest element, unlike lists or queues which are slower for this task.

3. Final Answer:

   Heap (Priority Queue) -> Option B

4. Quick Check:

   Priority queue = efficient min extraction [OK]

Hint: Use a heap to get smallest distance vertex fast [OK]

Common Mistakes:

• Using a simple list which is slow
• Using a queue which is FIFO, not min-based
• Using a set which has no order

3. What will be the output distances array after running Dijkstra's Algorithm from source vertex 0 on this graph represented by adjacency list with weights?

graph = {
  0: [(1, 4), (2, 1)],
  1: [(3, 1)],
  2: [(1, 2), (3, 5)],
  3: []
}

medium

A. [0, 4, 1, 6]

B. [0, 2, 1, 3]

C. [0, 3, 1, 4]

D. [0, 1, 2, 5]

Solution

1. Step 1: Initialize distances and start from vertex 0

   Distances: 0 to 0 = 0, others infinity initially. Update neighbors: vertex 1 = 4, vertex 2 = 1.

2. Step 2: Pick vertex with smallest distance (2), update neighbors

   From vertex 2, update vertex 1: min(4, 1+2=3) = 3, vertex 3 = 1+5=6.

3. Step 3: Pick vertex with smallest distance (1), update neighbors

   From vertex 1, update vertex 3: min(6, 3+1=4) = 4.

4. Step 4: Final distances

   Distances array is [0, 3, 1, 4].

5. Final Answer:

   [0, 3, 1, 4] -> Option C

6. Quick Check:

   Distances updated stepwise = [0, 3, 1, 4] [OK]

Hint: Update neighbors with min distance each step [OK]

Common Mistakes:

• Not updating vertex 1 distance from vertex 2
• Ignoring better path to vertex 3
• Mixing up edge weights

4. Consider this Dijkstra's Algorithm snippet in Python:

def dijkstra(graph, source):
    dist = {v: float('inf') for v in graph}
    dist[source] = 0
    visited = set()
    while len(visited) < len(graph):
        u = min((v for v in graph if v not in visited), key=lambda x: dist[x])
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

What is the main issue with it?

medium

A. The algorithm does not use a priority queue for efficiency

B. The visited set is not updated properly

C. The algorithm does not handle unreachable vertices

D. The algorithm does not update distances correctly

Solution

1. Step 1: Analyze the selection of next vertex

   The code uses min() over all unvisited vertices to find the smallest distance vertex, which is correct but inefficient.

2. Step 2: Identify efficiency problem

   Without a priority queue, each min() call takes O(V) time, making the algorithm slower but still correct logically.

3. Step 3: Check for correctness vs efficiency

   Though inefficient, the code updates distances and visited set correctly, so the main issue is lack of priority queue for efficiency.

4. Final Answer:

   The algorithm does not use a priority queue for efficiency -> Option A

5. Quick Check:

   Missing priority queue = inefficient but correct [OK]

Hint: Dijkstra needs priority queue for speed, else slow [OK]

Common Mistakes:

• Thinking visited set is not updated
• Assuming distance updates are wrong
• Confusing unreachable vertex handling

5. Given a weighted graph with negative edge weights but no negative cycles, why can't Dijkstra's Algorithm be used to find shortest paths from a source vertex?

hard

A. Because Dijkstra's Algorithm assumes all edge weights are non-negative

B. Because Dijkstra's Algorithm cannot handle graphs with cycles

C. Because Dijkstra's Algorithm requires the graph to be directed acyclic

D. Because Dijkstra's Algorithm only works on unweighted graphs

Solution

1. Step 1: Understand Dijkstra's assumption on edge weights

   Dijkstra's Algorithm assumes all edge weights are zero or positive to guarantee correctness.

2. Step 2: Explain why negative weights break the algorithm

   Negative weights can cause the algorithm to miss shorter paths found later, as it greedily picks the smallest tentative distance.

3. Step 3: Clarify other options

   The algorithm can handle cycles if no negative cycles exist, and it works on weighted graphs, not just unweighted.

4. Final Answer:

   Because Dijkstra's Algorithm assumes all edge weights are non-negative -> Option A

5. Quick Check:

   Negative weights break Dijkstra's assumptions [OK]

Hint: Dijkstra fails if any edge weight is negative [OK]

Common Mistakes:

• Thinking it can't handle cycles at all
• Believing it only works on unweighted graphs
• Confusing negative cycles with negative edges