Dijkstra’s Algorithm in Data Structures

When working with graphs in data structures, one common problem is finding the shortest path between nodes. Dijkstra’s Algorithm, named after Dutch computer scientist Edsger W. Dijkstra, is one of the most widely used algorithms for solving this problem.

It helps us efficiently calculate the minimum distance from a source vertex to all other vertices in a weighted graph, where edge weights are non-negative. In this DSA Tutorial, You can start to Learn Dijkstra’s Algorithm step by step. If you want to master other concepts try our Free DSA Course and win DSA.

Key Concepts of Dijkstra’s Algorithm

• Graph Representation: A graph consists of vertices (nodes) and edges (connections).
• Weighted Graph: Each edge has a weight (or cost) representing distance, time, or cost.
• Shortest Path Problem: The goal is to minimize the sum of weights along a path between two nodes.
• Greedy Approach: Dijkstra’s Algorithm uses a greedy strategy—choosing the next closest vertex at every step.

How Dijkstra’s Algorithm Works (Step-by-Step)

1. Start from the source node, setting its distance to 0 and all others to ∞.
2. Mark all nodes as unvisited.
3. Pick the unvisited node with the smallest distance.
4. Update the distance values of its neighbors.
5. Mark the current node as visited (it won’t be checked again).
6. Repeat until all nodes are visited or the shortest path is found.

Pseudocode of Dijkstra’s Algorithm

 
function Dijkstra(Graph, source):
    dist[source] ← 0
    for each vertex v in Graph:
        if v ≠ source:
            dist[v] ← ∞
        add v to unvisited set

    while unvisited is not empty:
        u ← vertex with smallest dist in unvisited
        remove u from unvisited

        for each neighbor v of u:
            alt ← dist[u] + weight(u, v)
            if alt < dist[v]:
                dist[v] ← alt

    return dist
  

Example

Consider the following weighted graph:

 
   (A)
  /   \
 2     5
 /       \
(B)---1---(C)
  

- Distance to B = 2 - Distance to C = min(5, 2+1=3) = 3 Final shortest paths: A → B = 2, A → C = 3

C++ Implementation

 
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

#define V 5

int minDistance(vector<int>& dist, vector<bool>& visited) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++) {
        if (!visited[v] && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

void dijkstra(int graph[V][V], int src) {
    vector<int> dist(V, INT_MAX);
    vector<bool> visited(V, false);
    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, visited);
        visited[u] = true;

        for (int v = 0; v < V; v++) {
            if (!visited[v] && graph[u][v] && dist[u] != INT_MAX &&
                dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    cout << "Vertex \t Distance from Source\n";
    for (int i = 0; i < V; i++) {
        cout << i << " \t " << dist[i] << "\n";
    }
}

int main() {
    int graph[V][V] = {
        {0, 10, 0, 0, 5},
        {0, 0, 1, 0, 2},
        {0, 0, 0, 4, 0},
        {7, 0, 6, 0, 0},
        {0, 3, 9, 2, 0}
    };
    dijkstra(graph, 0);
    return 0;
}
  

Python Implementation

 
import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

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

print(dijkstra(graph, 'A'))
  

Output:

 
{'A': 0, 'B': 2, 'C': 3}
  

Applications of Dijkstra’s Algorithm

• GPS Navigation Systems – Finding the shortest route between locations.
• Computer Networks – Determining optimal data routing.
• Airline/Travel Systems – Calculating cheapest/shortest routes.
• Game Development – AI pathfinding for characters.
• Project Planning – Optimizing task scheduling with dependencies.

Limitations of Dijkstra’s Algorithm

• Does not work with negative weight edges (use Bellman-Ford instead).
• Can be slower on dense graphs compared to other algorithms.
• Finds shortest paths from one source to all vertices, not between all pairs (Floyd-Warshall is better for that).

Conclusion

Dijkstra’s Algorithm is a fundamental shortest path algorithm in data structures and graph theory. Its greedy nature ensures efficient computation in weighted graphs with non-negative edges. From navigation systems to network routing, it forms the backbone of many real-world applications.

By mastering Dijkstra’s Algorithm, you gain deeper insights into graph theory, optimization, and real-world problem solving—making it an essential tool for programmers, computer scientists, and software engineers.

Take our Datastructures skill challenge to evaluate yourself!

In less than 5 minutes, with our skill challenge, you can identify your knowledge gaps and strengths in a given skill.

GET FREE CHALLENGE