Dijkstra's Algorithm Single Source Shortest Path in DSA C - Build from Scratch

Dijkstra's Algorithm Single Source Shortest Path

📖 Scenario: You are working as a city planner. You have a map of intersections connected by roads with distances. You want to find the shortest path from a starting intersection to all other intersections.

🎯 Goal: Build a program that uses Dijkstra's algorithm to find the shortest distance from a given start intersection to every other intersection in the city.

📋 What You'll Learn

Create a graph using an adjacency matrix with exact distances

Set a starting intersection index

Implement Dijkstra's algorithm to find shortest paths

Print the shortest distances from the start to all intersections

💡 Why This Matters

🌍 Real World

City planners and GPS systems use shortest path algorithms like Dijkstra's to find quickest routes between locations.

💼 Career

Understanding Dijkstra's algorithm is essential for software engineers working on navigation, mapping, and network routing applications.

1

Create the graph as an adjacency matrix

Create a 2D integer array called graph with 4 rows and 4 columns representing the distances between intersections. Use these exact values: row 0: 0, 5, 0, 10; row 1: 5, 0, 3, 0; row 2: 0, 3, 0, 1; row 3: 10, 0, 1, 0.

DSA C

# Create the adjacency matrix graph with the given distances
// Your code here

Hint

Use a 2D array with the exact distances for each row as shown.

2

Set the starting intersection index

Create an integer variable called start and set it to 0 to represent the starting intersection.

DSA C

#include 

int graph[4][4] = {
    {0, 5, 0, 10},
    {5, 0, 3, 0},
    {0, 3, 0, 1},
    {10, 0, 1, 0}
};

int main() {
    // Set the start intersection index
    // Your code here
    return 0;
}

Hint

Declare an integer variable named start and assign it the value 0.

3

Implement Dijkstra's algorithm to find shortest paths

Write the core logic of Dijkstra's algorithm inside main. Use arrays dist[4] to store shortest distances and visited[4] to track visited intersections. Initialize dist with a large number (e.g., 10000) except for dist[start] which is 0. Loop 4 times to pick the unvisited intersection with the smallest distance, mark it visited, and update distances to neighbors if shorter paths are found.

DSA C

#include 

int graph[4][4] = {
    {0, 5, 0, 10},
    {5, 0, 3, 0},
    {0, 3, 0, 1},
    {10, 0, 1, 0}
};

int main() {
    int start = 0;
    int dist[4];
    int visited[4] = {0};
    int i, j;

    // Initialize dist array
    // Your code here

    // Dijkstra's algorithm main loop
    // Your code here

    return 0;
}

Hint

Initialize distances to a large number except the start. Then repeat picking the closest unvisited node and update neighbors.

4

Print the shortest distances from the start

Add a for loop to print the shortest distances from start to each intersection using printf. Print exactly this format for each intersection i: Distance from 0 to i is dist[i] with a newline.

DSA C

Hint

Use a for loop and printf to show each distance in the exact format.