Dijkstra's Algorithm Single Source Shortest Path in DSA Python

Mental Model

Find the shortest path from one starting point to all other points by always choosing the closest unvisited point next.

Analogy: Imagine you are in a city and want to find the shortest way to every other place. You start from your home and always travel to the nearest place you haven't visited yet, updating your best known distances as you go.

Start: A
Graph:
A --2--> B
A --5--> C
B --1--> C
C --3--> D
D --1--> B

Distances:
A [0] -> B [∞] -> C [∞] -> D [∞]
↑ start

Dry Run Walkthrough

Input: Graph with edges: A-B(2), A-C(5), B-C(1), C-D(3), D-B(1); start at A

Goal: Find shortest distances from A to all nodes

Step 1: Start at A, set distance to 0, others to infinity

Distances: A[0], B[∞], C[∞], D[∞]; Visited: {}

Why: Initialize distances with start node zero and others unknown

Step 2: Visit A, update neighbors B and C distances

Distances: A[0], B[2], C[5], D[∞]; Visited: {A}

Why: From A, B is 2 away, C is 5 away; update these distances

Step 3: Choose unvisited node with smallest distance: B (2), visit B

Distances: A[0], B[2], C[3], D[∞]; Visited: {A, B}

Why: From B, C can be reached with distance 3 (2+1), which is better than 5

Step 4: Choose next closest unvisited node: C (3), visit C

Distances: A[0], B[2], C[3], D[6]; Visited: {A, B, C}

Why: From C, D can be reached with distance 6 (3+3)

Step 5: Choose next closest unvisited node: D (6), visit D

Distances: A[0], B[2], C[3], D[6]; Visited: {A, B, C, D}

Why: All nodes visited, shortest distances found

Result:

Final distances: A[0] -> B[2] -> C[3] -> D[6]

Annotated Code

DSA Python

import heapq

class Graph:
    def __init__(self):
        self.edges = {}

    def add_edge(self, from_node, to_node, weight):
        if from_node not in self.edges:
            self.edges[from_node] = []
        self.edges[from_node].append((to_node, weight))


def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph.edges}
    distances[start] = 0
    visited = set()
    heap = [(0, start)]  # (distance, node)

    while heap:
        current_distance, current_node = heapq.heappop(heap)
        if current_node in visited:
            continue
        visited.add(current_node)

        for neighbor, weight in graph.edges.get(current_node, []):
            distance = current_distance + weight
            if distance < distances.get(neighbor, float('inf')):
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))

    return distances


g = Graph()
g.add_edge('A', 'B', 2)
g.add_edge('A', 'C', 5)
g.add_edge('B', 'C', 1)
g.add_edge('C', 'D', 3)
g.add_edge('D', 'B', 1)

result = dijkstra(g, 'A')
for node in sorted(result):
    print(f"{node}: {result[node]}")

distances = {node: float('inf') for node in graph.edges}

Initialize all distances to infinity

distances[start] = 0

Distance to start node is zero

heap = [(0, start)]

Use a min-heap to pick closest unvisited node

current_distance, current_node = heapq.heappop(heap)

Pick node with smallest current distance

if current_node in visited: continue

Skip nodes already processed

visited.add(current_node)

Mark current node as visited

for neighbor, weight in graph.edges.get(current_node, []):

Check all neighbors of current node

if distance < distances.get(neighbor, float('inf')):

Update distance if found shorter path

heapq.heappush(heap, (distance, neighbor))

Add neighbor to heap with updated distance

Output

A: 0

B: 2

C: 3

D: 6

Complexity Analysis

Time: O(E log V) because each edge is checked and heap operations take log of number of vertices

Space: O(V + E) to store graph edges and distances

vs Alternative: Better than Bellman-Ford O(VE) for graphs without negative edges, faster due to priority queue

Edge Cases

Graph with no edges

Distances remain infinity except start node at zero

DSA Python

distances = {node: float('inf') for node in graph.edges}

Start node not in graph

Distance dictionary empty or only start with zero, no neighbors processed

DSA Python

distances[start] = 0

Disconnected nodes

Distances to unreachable nodes remain infinity

DSA Python

for neighbor, weight in graph.edges.get(current_node, [])

When to Use This Pattern

When asked to find shortest paths from one point to all others in a weighted graph without negative edges, reach for Dijkstra's algorithm because it efficiently finds minimum distances using a priority queue.

Common Mistakes

Mistake: Not using a priority queue and scanning all nodes repeatedly
Fix: Use a min-heap to always pick the closest unvisited node next

Mistake: Updating distances without checking if new distance is smaller
Fix: Only update and push to heap if new distance is less than current known distance

Mistake: Not marking nodes as visited and processing them multiple times
Fix: Keep a visited set and skip nodes already processed

Summary

Finds shortest distances from one start node to all others in a weighted graph without negative edges.

Use when you need efficient shortest path calculations from a single source in graphs with non-negative weights.

Always pick the closest unvisited node next and update neighbors to find shortest paths step by step.

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