Dijkstra's Algorithm Single Source Shortest Path in DSA C - Deep Dive

Overview - Dijkstra's Algorithm Single Source Shortest Path

What is it?

Dijkstra's Algorithm finds the shortest path from one starting point to all other points in a network or graph. It works by exploring paths step-by-step, always choosing the closest unvisited point next. This helps find the quickest route in maps, networks, or any system with connected points. It only works with graphs that have no negative distances.

Why it matters

Without Dijkstra's Algorithm, finding the shortest or fastest route in complex networks would be slow and inefficient. Imagine trying to find the quickest way home without a map or GPS; it would take much longer and be confusing. This algorithm makes navigation, routing, and planning fast and reliable, impacting everything from GPS apps to internet data flow.

Where it fits

Before learning Dijkstra's Algorithm, you should understand basic graph concepts like nodes and edges, and simple data structures like arrays and priority queues. After mastering it, you can explore more advanced shortest path algorithms like A* or Bellman-Ford, and graph optimization techniques.

Mental Model

Core Idea

Always pick the closest unvisited point and update paths until all shortest distances from the start are found.

Think of it like...

Imagine you are in a city and want to visit all other neighborhoods starting from your home. You always travel next to the closest neighborhood you haven't visited yet, updating your knowledge of the shortest ways to get there.

Start (S)
  |
  v
[Node A] --5--> [Node B]
  |              |
  2              1
  |              |
[Node C] --3--> [Node D]

Process:
S -> closest unvisited node -> update distances -> repeat until all visited

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Distances

Concept: Learn what graphs are and how distances between points are represented.

A graph is a collection of points called nodes connected by lines called edges. Each edge can have a distance or cost. For example, a map with cities (nodes) connected by roads (edges) with lengths (distances).

Result

You can represent a network of connected points with distances, ready for pathfinding.

Understanding the structure of graphs and distances is essential because Dijkstra's Algorithm works by exploring these connections.

2

Foundation

Basics of Tracking Shortest Paths

Concept: Learn how to keep track of the shortest known distance to each node from the start.

We keep a list of distances, starting with zero for the start node and infinity for others. As we explore, we update these distances when we find a shorter path.

Result

A system to remember the best known routes to each point as we explore the graph.

Tracking distances lets us compare and improve paths, which is the core of finding shortest routes.

3

Intermediate

Using a Priority Queue to Pick Closest Node

🤔Before reading on: Do you think picking nodes randomly or always the closest first leads to correct shortest paths? Commit to your answer.

Concept: Introduce a priority queue to always select the next closest unvisited node efficiently.

A priority queue is a data structure that always gives you the smallest element quickly. We use it to pick the node with the smallest current distance to explore next, ensuring we build shortest paths step-by-step.

Result

Efficiently selecting the next node to explore speeds up the algorithm and guarantees correctness.

Knowing that always picking the closest node next ensures we never miss a shorter path is key to Dijkstra's success.

4

Intermediate

Relaxing Edges to Update Distances

🤔Before reading on: Do you think updating distances only when a shorter path is found is necessary? Commit to your answer.

Concept: Learn the process of 'relaxing' edges, which means updating the shortest distance to neighbors if a better path is found.

For each neighbor of the current node, check if going through the current node offers a shorter path. If yes, update the neighbor's distance and add it to the priority queue.

Result

Distances get improved step-by-step, ensuring the shortest paths are found.

Understanding relaxation is crucial because it is how the algorithm improves paths and converges to the shortest solution.

5

Intermediate

Handling Visited Nodes to Avoid Reprocessing

Concept: Learn why and how to mark nodes as visited to prevent unnecessary work.

Once a node's shortest distance is finalized, we mark it visited and do not revisit it. This avoids loops and repeated work, making the algorithm efficient.

Result

The algorithm finishes faster and correctly by not revisiting nodes.

Knowing when a node's shortest path is final prevents wasted effort and infinite loops.

6

Advanced

Implementing Dijkstra's Algorithm in C

🤔Before reading on: Do you think arrays alone are enough for efficient Dijkstra's implementation? Commit to your answer.

Concept: Combine all concepts into a working C program using arrays and a priority queue (min-heap) to find shortest paths.

Use an adjacency list to represent the graph. Use a min-heap priority queue to pick the closest node. Initialize distances, relax edges, and mark visited nodes until all shortest paths are found. Example code snippet: #include #include #include #define MAX_NODES 100 typedef struct Edge { int to; int weight; struct Edge* next; } Edge; typedef struct { Edge* head[MAX_NODES]; int num_nodes; } Graph; int dist[MAX_NODES]; int visited[MAX_NODES]; // Priority queue and graph functions omitted for brevity void dijkstra(Graph* g, int start) { for (int i = 0; i < g->num_nodes; i++) { dist[i] = INT_MAX; visited[i] = 0; } dist[start] = 0; // Initialize priority queue and insert start // While queue not empty: // Extract min distance node u // If visited[u] continue // Mark visited[u] // For each neighbor v of u: // If dist[u] + weight(u,v) < dist[v]: // Update dist[v] // Insert v into queue } int main() { // Build graph, call dijkstra, print distances return 0; }

Result

A complete program that prints shortest distances from the start node to all others.

Seeing the full implementation connects theory to practice and reveals how data structures work together.

7

Expert

Optimizations and Limitations of Dijkstra's Algorithm

🤔Before reading on: Do you think Dijkstra's Algorithm works correctly with negative edge weights? Commit to your answer.

Concept: Explore why Dijkstra's Algorithm cannot handle negative edges and how to optimize it for large graphs.

Dijkstra assumes all edge weights are non-negative because it picks the closest node first. Negative edges can cause it to miss shorter paths. For large graphs, using a Fibonacci heap can improve performance. Also, bidirectional search can speed up queries in practice.

Result

Understanding these limits helps choose the right algorithm and optimize performance.

Knowing when Dijkstra fails and how to optimize it prevents costly mistakes in real applications.

Under the Hood

Dijkstra's Algorithm maintains a set of nodes with known shortest distances from the start. It uses a priority queue to pick the node with the smallest tentative distance. When a node is picked, its neighbors are checked and their distances updated if a shorter path is found (relaxation). This process repeats until all nodes are visited or the queue is empty. Internally, the priority queue operations and adjacency list traversal determine efficiency.

Why designed this way?

The algorithm was designed to efficiently find shortest paths without exploring all possible routes. By always choosing the closest unvisited node, it guarantees that once a node is visited, its shortest path is final. Alternatives like Bellman-Ford handle negative edges but are slower. The design balances correctness and speed for graphs with non-negative weights.

┌───────────────┐
│ Start Node (S)│
└──────┬────────┘
       │
       ▼
┌───────────────┐       ┌───────────────┐
│ Pick closest  │──────▶│ Relax neighbors│
│ unvisited node│       └──────┬────────┘
└──────┬────────┘              │
       │                       ▼
       │               ┌───────────────┐
       │               │ Update distances│
       │               └──────┬────────┘
       │                      │
       │                      ▼
       │               ┌───────────────┐
       └──────────────▶│ Mark visited  │
                       └──────┬────────┘
                              │
                              ▼
                      ┌───────────────┐
                      │ Repeat until  │
                      │ all visited   │
                      └───────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does Dijkstra's Algorithm work correctly with negative edge weights? Commit to yes or no.

Common Belief: Dijkstra's Algorithm can handle any edge weights, including negative ones.

Reality: Dijkstra's Algorithm only works correctly with non-negative edge weights. Negative edges can cause it to find wrong shortest paths.

Why it matters: Using Dijkstra on graphs with negative edges can lead to incorrect routing decisions, causing failures in navigation or network systems.

Quick: Is it necessary to update distances for all neighbors every time a node is visited? Commit to yes or no.

Common Belief: You must update distances for all neighbors every time you visit a node, even if the new path is longer.

Reality: Distances are only updated if the new path is shorter than the current known distance (relaxation).

Why it matters: Updating distances unnecessarily wastes time and can cause incorrect results or infinite loops.

Quick: Does the order of visiting nodes in Dijkstra's Algorithm affect the correctness of the shortest paths? Commit to yes or no.

Common Belief: The order of visiting nodes does not matter as long as all nodes are eventually visited.

Reality: The order matters; always visiting the closest unvisited node first ensures correctness.

Why it matters: Visiting nodes in the wrong order can cause the algorithm to miss shorter paths and produce wrong results.

Expert Zone

1

Dijkstra's Algorithm can be optimized with different priority queue implementations, like Fibonacci heaps, to reduce time complexity from O((V+E) log V) to O(E + V log V).

2

In practice, bidirectional Dijkstra runs two simultaneous searches from start and end nodes, meeting in the middle to speed up shortest path queries.

3

When edge weights are uniform, simpler algorithms like Breadth-First Search (BFS) can find shortest paths more efficiently.

When NOT to use

Do not use Dijkstra's Algorithm if the graph has negative edge weights; instead, use Bellman-Ford. For very large graphs with frequent queries, consider A* or bidirectional search. If edges have uniform weights, BFS is simpler and faster.

Production Patterns

Dijkstra's Algorithm is widely used in GPS navigation systems, network routing protocols like OSPF, and game AI pathfinding. In production, it is often combined with heuristics or run on preprocessed graphs to improve speed.

Connections

Bellman-Ford Algorithm

Alternative shortest path algorithm that handles negative edges.

Understanding Dijkstra's limitations helps appreciate Bellman-Ford's ability to handle negative weights at the cost of speed.

Priority Queue Data Structure

Core data structure used to efficiently select the next node to explore.

Mastering priority queues is essential to implementing Dijkstra efficiently and understanding many other algorithms.

Supply Chain Logistics

Both involve finding optimal routes and minimizing costs in networks.

Knowing how shortest path algorithms work can improve understanding of real-world logistics and transportation planning.

Common Pitfalls

#1 Using Dijkstra's Algorithm on graphs with negative edge weights.

Wrong approach:

Run Dijkstra on a graph where some edges have negative distances, expecting correct shortest paths.

Correct approach:

Use Bellman-Ford Algorithm for graphs with negative edges to correctly find shortest paths.

Root cause:

Misunderstanding that Dijkstra assumes all edge weights are non-negative for correctness.

#2 Not updating distances only when a shorter path is found.

Wrong approach:

Always update neighbor distances regardless of whether the new path is shorter.
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
else {
dist[v] = dist[u] + weight; // Incorrect: overwrites even if longer
}

Correct approach:

Update distances only if the new path is shorter.
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}

Root cause:

Confusing relaxation step logic and ignoring the need to keep shortest distances.

#3 Revisiting nodes after their shortest distance is finalized.

Wrong approach:

Do not mark nodes as visited and process them multiple times, causing inefficiency.
while (!queue_empty) {
node = extract_min();
// No visited check
process(node);
}

Correct approach:

Mark nodes as visited after extracting from queue and skip if already visited.
while (!queue_empty) {
node = extract_min();
if (visited[node]) continue;
visited[node] = 1;
process(node);
}

Root cause:

Not understanding that once a node's shortest path is found, it should not be reconsidered.

Key Takeaways

Dijkstra's Algorithm finds shortest paths by always exploring the closest unvisited node next.

It requires non-negative edge weights to guarantee correct shortest paths.

Using a priority queue to pick the next node makes the algorithm efficient.

Relaxation updates distances only when a shorter path is found, ensuring accuracy.

Marking nodes as visited prevents unnecessary work and infinite loops.

Practice

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

easy

A. To sort the vertices of a graph topologically

B. To find the minimum spanning tree of a graph

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 goal of Dijkstra's Algorithm

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

2. Step 2: Compare with other graph algorithms

   Minimum spanning tree algorithms find a tree connecting all vertices with minimum total edge weight, cycle detection finds loops, and topological sort orders vertices in directed acyclic graphs. These are different goals.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Confusing with minimum spanning tree algorithms
• Thinking it detects cycles
• Assuming it sorts vertices

2. Which of the following is the correct way to initialize the distance array in Dijkstra's Algorithm in C?

easy

A. int dist[V]; for(int i=0; i

B. int dist[V] = {INT_MAX};

C. int dist[V] = {0};

D. int dist[V] = NULL;

Solution

1. Step 1: Understand distance initialization

   Distances should start as infinity (or a very large number) except the source vertex, to represent unknown shortest paths.

2. Step 2: Check each option

   int dist[V] = {0}; initializes all distances to 0, which is incorrect. int dist[V]; for(int i=0; i

3. Final Answer:

   int dist[V]; for(int i=0; i -> Option A

4. Quick Check:

   Initialize distances to INT_MAX with loop [OK]

Hint: Use loop to set all distances to INT_MAX [OK]

Common Mistakes:

• Using {INT_MAX} initializes only first element
• Setting all distances to 0
• Assigning NULL to int array

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

int graph[4][4] = {
  {0, 1, 4, 0},
  {1, 0, 2, 6},
  {4, 2, 0, 3},
  {0, 6, 3, 0}
};

medium

A. [0, 1, 4, 7]

B. [0, 1, 3, 5]

C. [0, 1, 3, 6]

D. [0, 2, 4, 6]

Solution

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

   Distances: dist[0]=0, dist[1]=∞, dist[2]=∞, dist[3]=∞. Update neighbors of 0: dist[1]=1, dist[2]=4.

2. Step 2: Pick vertex with smallest tentative distance and update neighbors

   Pick vertex 1 (dist=1). Update dist[2] = min(4, 1+2=3) = 3, dist[3] = min(∞, 1+6=7) = 7. Next pick vertex 2 (dist=3). Update dist[3] = min(7, 3+3=6) = 6. Finally pick vertex 3 (dist=6).

3. Final Answer:

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

4. Quick Check:

   Distances after relaxation = [0,1,3,6] [OK]

Hint: Relax edges stepwise, pick smallest distance vertex next [OK]

Common Mistakes:

• Not updating distances after relaxation
• Choosing wrong next vertex
• Ignoring shorter paths through intermediate vertices

4. Identify the error in the following snippet of Dijkstra's Algorithm in C:

for (int count = 0; count < V-1; count++) {
  int u = minDistance(dist, sptSet);
  sptSet[u] = 1;
  for (int v = 0; v < V; v++) {
    if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
      dist[v] = dist[u] + graph[u][v];
    }
  }
}

medium

A. The loop should run from 1 to V instead of 0 to V-1

B. The condition 'graph[u][v]' should be 'graph[u][v] != 0' to check edge existence

C. The sptSet array should be initialized with 1 instead of 0

D. The dist[u] check should be 'dist[u] == INT_MAX' instead of '!='

Solution

1. Step 1: Analyze edge existence condition

   The condition 'graph[u][v]' relies on implicit truthiness of non-zero values. In C, this works but is less clear. Using 'graph[u][v] != 0' explicitly checks for edge presence and improves readability.

2. Step 2: Check other conditions

   Loop range from 0 to V-1 is correct for V vertices. sptSet should start with 0 (false). The dist[u] check must be '!= INT_MAX' to ensure u is reachable before relaxing edges.

3. Final Answer:

   The condition 'graph[u][v]' should be 'graph[u][v] != 0' to check edge existence -> Option B

4. Quick Check:

   Explicit edge check improves clarity [OK]

Hint: Use explicit '!= 0' to check edges in adjacency matrix [OK]

Common Mistakes:

• Assuming loop range is wrong
• Initializing sptSet incorrectly
• Reversing dist[u] check logic

5. Given a weighted graph with vertices 0 to 5 and edges:

0-1: 7, 0-2: 9, 0-5: 14, 1-2: 10, 1-3: 15, 2-3: 11, 2-5: 2, 3-4: 6, 4-5: 9

Using Dijkstra's Algorithm from source 0, what is the shortest distance to vertex 4?

hard

A. 20

B. 26

C. 21

D. 19

Solution

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

   dist[0]=0, others = ∞. Update neighbors: dist[1]=7, dist[2]=9, dist[5]=14.

2. Step 2: Pick vertex with smallest dist and update neighbors

   Pick 1 (7): update dist[3] = min(∞, 7+15=22) = 22. Pick 2 (9): update dist[3] = min(22, 9+11=20) = 20, dist[5] = min(14, 9+2=11) = 11. Pick 5 (11): update dist[4] = min(∞, 11+9=20) = 20. Pick 3 (20): update dist[4] = min(20, 20+6=26) = 20. Pick 4 (20).

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Shortest path to 4 = 20 [OK]

Hint: Relax edges carefully, update shortest distances stepwise [OK]

Common Mistakes:

• Not updating dist[5] to smaller value
• Ignoring shorter path through vertex 2
• Adding edges incorrectly