Dijkstra's Algorithm in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
#define V 5
#define INF 9999
int minD(int d[], int v[]) {
    int m = INF, i, idx = -1;
    for (i = 0; i < V; i++)
        if (!v[i] && d[i] <= m) m = d[i], idx = i;
    return idx;
}
void dijkstra(int g[V][V], int s) {
    int d[V], v[V] = {0};
    for (int i = 0; i < V; i++) d[i] = INF;
    d[s] = 0;
    for (int c = 0; c < V - 1; c++) {
        int u = minD(d, v);
        v[u] = 1;
        for (int i = 0; i < V; i++)
            if (!v[i] && g[u][i] && d[u] + g[u][i] < d[i])
                d[i] = d[u] + g[u][i];
    }
    for (int i = 0; i < V; i++)
        printf("%d ", d[i]);
}
int main() {
    int g[V][V] = {
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0}
    };
    dijkstra(g, 0);
}

C Output

Input:
Graph with 5 vertices. Start from node 0.
Output:
Input: Adjacency matrix, Source: 0
Output: 0 2 5 6 7

C++ Program

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> P;
void dijkstra(int n, vector<P> g[], int s) {
    vector<int> d(n, 1e9); d[s] = 0;
    priority_queue<P, vector<P>, greater<>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        for (auto [v, w] : g[u])
            if (d[u] + w < d[v])
                d[v] = d[u] + w, pq.push({d[v], v});
    }
    for (int x : d) cout << x << " ";
}
int main() {
    int n = 4;
    vector<P> g[4];
    g[0] = {{1, 1}, {2, 4}};
    g[1] = {{2, 2}, {3, 6}};
    g[2] = {{3, 3}};
    dijkstra(n, g, 0);
}

C++ Output

Input:
Graph: 0→1(1), 0→2(4), 1→2(2), 1→3(6), 2→3(3). Source: 0
Output:
Input: 0→1,2 | 1→2,3 | 2→3
Output: 0 1 3 6

JAVA Program

import java.util.*;
class Main {
    public static void dijkstra(List<int[]>[] g, int s) {
        int[] d = new int[g.length];
        Arrays.fill(d, Integer.MAX_VALUE);
        d[s] = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        q.add(new int[]{0, s});
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] e : g[cur[1]])
                if (d[cur[1]] + e[1] < d[e[0]]) {
                    d[e[0]] = d[cur[1]] + e[1];
                    q.add(new int[]{d[e[0]], e[0]});
                }
        }
        for (int x : d) System.out.print(x + " ");
    }
    public static void main(String[] args) {
        List<int[]>[] g = new ArrayList[3];
        for (int i = 0; i < 3; i++) g[i] = new ArrayList<>();
        g[0].add(new int[]{1, 2});
        g[0].add(new int[]{2, 4});
        g[1].add(new int[]{2, 1});
        dijkstra(g, 0);
    }
}

JAVA Output

Input:
Graph: 0→1(2), 0→2(4), 1→2(1). Source: 0
Output:
Input: 0→1→2
Output: 0 2 3

Python Program

import heapq
g = {0: [(1, 10), (2, 3)], 1: [(3, 2)], 2: [(1, 1), (3, 8)], 3: []}
def dijkstra(g, s):
    d = {v: float('inf') for v in g}; d[s] = 0
    q = [(0, s)]
    while q:
        du, u = heapq.heappop(q)
        for v, w in g[u]:
            if d[u] + w < d[v]:
                d[v] = d[u] + w
                heapq.heappush(q, (d[v], v))
    print(' '.join(str(d[v]) for v in sorted(g)))
dijkstra(g, 0)

Python Output

Input:
Graph: 0→1(10), 0→2(3), 2→1(1), 1→3(2), 2→3(8). Source: 0

Output:
Input: 0→2→1→3
Output: 0 4 3 6

In-Depth Explanation

Example

In the Python example:

0 → 1 (10)

0 → 2 (3)

2 → 1 (1)

1 → 3 (2)

2 → 3 (8)

Rather than taking 0→1→3, we see that 0→2→1→3 is cheaper with total cost = 6. Dijkstra does this by incrementally updating each node's shortest path in a greedy manner using a priority queue.

Real-Life Analogy

Consider navigating to work using Google Maps. You'd like the smallest time or distance — and preferably not the fewest turns. Dijkstra's Algorithm does the same: it determines the shortest cost route to each destination from where you are, examining all paths and always taking the closest next step.

Why It Matters

This is a fundamental algorithm in:

Network routing (shortest path in a mesh)

GPS/Map programs

Robotics (path planning)

Game AI (NPC movement)

Airline scheduling systems

It guarantees you're always making the best decision at the moment while ensuring global optimality.

Learning Insights

You'll learn:

Greedy algorithms in graphs

Use of priority queues (min-heaps) for performance

The concept of visited vs updated (we don't go back on shorter paths)

How weights modify the traversal logic

Dijkstra is different from BFS in that it takes cost/weight into consideration — BFS only works on unweighted graphs or graphs with equal weights.

Interview & Real-World Use

This is a popular interview question, commonly asked in:

Graph-based algorithm rounds

Shortest-path or weighted optimization problems

Real-time systems and route planning

Real-world applications:

Internet packet routing

Map apps and logistics (Uber, FedEx)

Robotics and automated warehousing

Emergency route planning and AI pathfinding

Dijkstra's Algorithm is considered one of the most significant and widely-applied algorithms for shortest path finding in weighted graphs. It finds applications in GPS navigation, network routing, artificial intelligence, and game engines. The minimal and optimized C, C++, Java, and Python implementations provided show how to construct greedy solutions based on priority. It is important to know how Dijkstra works in order to master coding interviews and tackle actual optimization problems related to paths, costs, and choices over graphs.