Dijkstra's Algorithm Single Source Shortest Path in DSA Go - 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 pick the next node with the smallest distance?

A priority queue (or min-heap) is used to efficiently select the node with the smallest current distance.

intermediate

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 change. Negative edges can create shorter paths later, breaking this assumption.

advanced

What is the time complexity of Dijkstra's Algorithm using a priority queue?

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

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

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

A Non-negative edge weights

B Negative edge weights

C Only unweighted edges

D Directed edges only

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

Which data structure helps Dijkstra's Algorithm efficiently select the next node to process?

A Priority queue

B Stack

C Queue

D Linked list

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

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

A Edges are reversed

B Nodes are removed from the graph

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

D The algorithm terminates

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 Infinity

B Zero

C Negative one

D Undefined

The source node distance is zero because it is the starting point.

If a graph has negative edge weights, which algorithm is better than Dijkstra's?

A Breadth First Search

B Depth First Search

C Prim's Algorithm

D Bellman-Ford Algorithm

Bellman-Ford can handle negative edge weights and detect negative cycles.

Describe step-by-step how Dijkstra's Algorithm finds the shortest paths from a source node.

Think about starting from the source and exploring neighbors while updating shortest distances.

Explain why Dijkstra's Algorithm cannot be used with negative edge weights and what could happen if it is used anyway.

Consider the effect of negative edges on the shortest path assumption.

Practice

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

easy

A. To detect cycles in a graph

B. To find the maximum flow in a network

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

D. To sort the vertices in topological order

Solution

1. Step 1: Understand the algorithm's goal

   Dijkstra's Algorithm is designed to find the shortest paths from one starting point (source) to all other points in a graph with non-negative edge weights.

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 C

4. Quick Check:

   Dijkstra's Algorithm = shortest path from source [OK]

Hint: Remember: Dijkstra finds shortest paths from one source [OK]

Common Mistakes:

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

2. Which Go data structure is most suitable to implement the priority queue needed in Dijkstra's Algorithm?

easy

A. container/heap package's IntHeap implementation

B. slice with manual sorting

C. map[string]int for distances

D. linked list for adjacency representation

Solution

1. Step 1: Identify priority queue requirement

   Dijkstra's Algorithm requires a priority queue to efficiently get the vertex with the smallest tentative distance.

2. Step 2: Choose Go's best priority queue

   Go's standard library provides the container/heap package which supports heap operations. Using IntHeap or a custom heap is the best choice for priority queue.

3. Final Answer:

   container/heap package's IntHeap implementation -> Option A

4. Quick Check:

   Priority queue in Go = container/heap [OK]

Hint: Use container/heap for priority queue in Go [OK]

Common Mistakes:

• Using slice without heap operations (slow)
• Using map for priority queue (wrong type)
• Using linked list for priority queue

3. What is the output of the following Go code snippet implementing Dijkstra's Algorithm for a graph with vertices 0,1,2 and edges: 0->1 (4), 0->2 (1), 2->1 (2)?

dist := []int{1e9, 1e9, 1e9}
dist[0] = 0
pq := &IntHeap{{0, 0}} // {distance, vertex}
heap.Init(pq)
for pq.Len() > 0 {
  cur := heap.Pop(pq).(Pair)
  d, u := cur.distance, cur.vertex
  if d > dist[u] { continue }
  for _, e := range graph[u] {
    v, w := e.vertex, e.weight
    if dist[u]+w < dist[v] {
      dist[v] = dist[u] + w
      heap.Push(pq, Pair{dist[v], v})
    }
  }
}
fmt.Println(dist)

medium

A. [0 4 1]

B. [0 3 1]

C. [0 6 1]

D. [1 3 1]

Solution

1. Step 1: Initialize distances and priority queue

   Distances start as [inf, inf, inf], then dist[0] = 0. Priority queue starts with vertex 0 at distance 0.

2. Step 2: Relax edges step-by-step

   From 0: dist[1] = min(inf, 0+4)=4, dist[2] = min(inf, 0+1)=1. Push (4,1) and (1,2). Next pop (1,2): from 2 to 1: dist[1] = min(4,1+2)=3. Update dist[1] to 3. Final distances: [0,3,1].

3. Final Answer:

   [0 3 1] -> Option B

4. Quick Check:

   Shortest distances = [0 3 1] [OK]

Hint: Relax edges and update distances carefully [OK]

Common Mistakes:

• Not updating dist[1] after checking edge 2->1
• Mixing up vertex indices
• Ignoring priority queue order

4. Identify the bug in this Go snippet of Dijkstra's Algorithm:

dist := make([]int, n)
for i := range dist {
  dist[i] = 1e9
}
dist[src] = 0
pq := &IntHeap{{0, src}}
heap.Init(pq)
for pq.Len() > 0 {
  cur := heap.Pop(pq).(Pair)
  d, u := cur.distance, cur.vertex
  if d < dist[u] { continue }
  for _, e := range graph[u] {
    v, w := e.vertex, e.weight
    if dist[u]+w < dist[v] {
      dist[v] = dist[u] + w
      heap.Push(pq, Pair{dist[v], v})
    }
  }
}

medium

A. The graph edges are not relaxed properly

B. dist array is not initialized with large values

C. Priority queue is not initialized before use

D. The condition should be 'if d > dist[u]' instead of 'if d < dist[u]'

Solution

1. Step 1: Check the distance comparison condition

   The condition 'if d < dist[u]' is incorrect because we want to skip processing if the current distance is greater than the stored distance.

2. Step 2: Correct condition for skipping outdated entries

   The correct condition is 'if d > dist[u]' to ignore stale entries in the priority queue.

3. Final Answer:

   The condition should be 'if d > dist[u]' instead of 'if d < dist[u]' -> Option D

4. Quick Check:

   Skip outdated if d > dist[u] [OK]

Hint: Skip if current distance is greater, not smaller [OK]

Common Mistakes:

• Using wrong comparison operator in distance check
• Not initializing dist with large values
• Forgetting to initialize priority queue

5. Given a weighted graph with vertices 0 to 4 and edges: 0->1 (2), 0->2 (4), 1->2 (1), 1->3 (7), 2->4 (3), 3->4 (1), Use Dijkstra's Algorithm to find the shortest path distance from vertex 0 to vertex 4. What is the shortest distance?

hard

A. 6

B. 7

C. 8

D. 5

Solution

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

   distances: [0, inf, inf, inf, inf]. From 0: dist[1]=2, dist[2]=4.

2. Step 2: Relax edges from vertex 1 and 2

   From 1: dist[2]=min(4,2+1)=3, dist[3]=2+7=9. From 2: dist[4]=3+3=6.

3. Step 3: Relax edges from vertex 3

   From 3: dist[4]=min(6,9+1=10)=6 (no change).

4. Final Answer:

   6 -> Option A

5. Quick Check:

   Shortest path 0->1->2->4 = 6 [OK]

Hint: Check all paths and pick minimum sum of edges [OK]

Common Mistakes:

• Ignoring shorter path through vertex 2
• Adding edges incorrectly
• Not updating distances after relaxation