Dijkstra's Algorithm

Graphs O(V²) O(V)

Finds the shortest path from a source node to every other node in a weighted graph with non-negative edges.

Source

1/28

Initialise every distance to ∞.

InvariantEvery visited node has its final shortest distance. That holds only because no edge weight is negative.

currentfrontiervisitedtree edge

dijkstra.c

#define V 6
#define INF 1000000
 
void dijkstra(int graph[V][V], int src, int dist[V]) {
    int visited[V] = {0};
    for (int i = 0; i < V; i++) dist[i] = INF;
    dist[src] = 0;
 
    for (int count = 0; count < V - 1; count++) {
        int u = -1;
        for (int v = 0; v < V; v++)
            if (!visited[v] && (u == -1 || dist[v] < dist[u]))
                u = v;
        visited[u] = 1;
 
        for (int v = 0; v < V; v++)
            if (graph[u][v] && !visited[v] &&
                dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }
}

How Dijkstra's Algorithm works

Grow a set of nodes with known shortest distances. Always settle the unvisited node with the smallest tentative distance, then relax its edges — a settled distance can never improve because all edges are non-negative.

Worst case

O(V²) with the array scan shown here; O(E log V) with a priority queue.

When to use it

Single-source shortest paths with non-negative weights: routing, maps, network costs.