Dijkstra Principles and Implementation

Prerequisite Knowledge

Before reading this article, you should first learn:

Summary in One Sentence

Dijkstra's algorithm is used to find the shortest path from one node to all others in a graph. It is basically the standard BFS algorithm plus a greedy idea.

If the graph has negative weight edges, the greedy idea will not work, so Dijkstra's algorithm can only handle graphs without negative weight edges.

There are only two differences between Dijkstra's algorithm and standard BFS:

Standard BFS uses a regular queue. Dijkstra uses a priority queue, so nodes closer to the start are processed first (this is the greedy idea).
Standard BFS uses a visited array to record visited nodes to avoid getting stuck in a loop. Dijkstra uses a distTo array which also avoids loops and saves the shortest path from the start to every node.

In Overview of Shortest Path Algorithms in Graphs, we gave a brief introduction to shortest path problems, the difference between single-source and multi-source shortest paths, the problem with negative weight edges, and some classic shortest path algorithms including Dijkstra. In this article, we will cover:

How to build Dijkstra's algorithm based on the standard Graph BFS Traversal Algorithm.
Detailed explanation of how Dijkstra's algorithm works and why it is correct.
The shortest path between two points is a special case of the single-source shortest path. We can slightly change Dijkstra's algorithm to make it faster.

After you understand the logic and code, the next article will show how to change standard Dijkstra code to solve harder shortest path problems with more conditions.

We will use the graph interfaces defined in Graph Basics and General Implementation. Please read that part first to know how graphs are stored and defined.

Let's start.

Dijkstra Algorithm Code

Let's start with the code. We only need to make a few changes to the standard BFS algorithm to get Dijkstra, so it's simple. We will first see what changes are needed, then explain why they work.

In Graph BFS Traversal Algorithm, we showed three ways to write BFS. The third one is best for Dijkstra, because we need to track the shortest path from the start to each visited node.

Here is the standard graph BFS traversal algorithm:

java

// BFS traversal of a graph, starting from node s and recording the number
// of steps (the number of edges from the start node s to the current node)
// Each node maintains its own State class to record the number of steps from s
class State {
    // Current node ID
    int node;
    // Number of steps from the start node s to the current node
    int step;

    public State(int node, int step) {
        this.node = node;
        this.step = step;
    }
}


void bfs(Graph graph, int s) {
    boolean[] visited = new boolean[graph.size()];
    Queue<State> q = new LinkedList<>();

    q.offer(new State(s, 0));
    visited[s] = true;

    while (!q.isEmpty()) {
        State state = q.poll();
        int cur = state.node;
        int step = state.step;
        System.out.println("visit " + cur + " with step " + step);
        for (Edge e : graph.neighbors(cur)) {
            if (visited[e.to]) { 
                continue;
            }
            q.offer(new State(e.to, step + 1));
            visited[e.to] = true;
        }
    }
}

cpp

// BFS traversal of a graph structure, starting from node s and recording the
// number of steps (the number of edges from the start node s to the current node)
// Each node maintains its own State class to record the number of steps from s
class State {
public:
    // Current node ID
    int node;
    // Number of steps from the start node s to the current node
    int step;

    State(int node, int step) : node(node), step(step) {}
};

void bfs(const Graph& graph, int s) {
    vector<bool> visited(graph.size(), false);
    queue<State> q;

    q.push(State(s, 0));
    visited[s] = true;

    while (!q.empty()) {
        State state = q.front();
        q.pop();
        int cur = state.node;
        int step = state.step;
        cout << "visit " << cur << " with step " << step << endl;
        for (const Edge& e : graph.neighbors(cur)) {
            if (visited[e.to]) {
                continue;
            }
            q.push(State(e.to, step + 1));
            visited[e.to] = true;
        }
    }
}

python

# BFS traversal of a graph structure, starting BFS from node s and recording the
# number of steps (the number of edges from the start node s to the current node)
# Each node maintains its own State class, recording the number of steps from s
class State:
    def __init__(self, node, step):
        # Current node ID
        self.node = node
        # Number of steps from the start node s to the current node
        self.step = step


def bfs(graph, s):
    visited = [False] * len(graph)
    from collections import deque

    q = deque([State(s, 0)])
    visited[s] = True

    while q:
        state = q.popleft()
        cur = state.node
        step = state.step
        print(f"visit {cur} with step {step}")
        for e in graph.neighbors(cur):
            if visited[e.to]:  
                continue
            q.append(State(e.to, step + 1))
            visited[e.to] = True

// BFS traversal of a graph structure, starting from node s and recording the
// number of steps (the number of edges from the start node s to the current node)
// Each node maintains its own State class, recording the number of steps from s
type State struct {
    // Current node ID
    node   int
    // Number of steps from the start node s to the current node
    step int
}

func bfs(graph Graph, s int) {
    visited := make([]bool, graph.size())
    q := []*State{{s, 0}}
    visited[s] = true
    for len(q) > 0 {
        state := q[0]
        q = q[1:]
        cur := state.node
        step := state.step
        fmt.Printf("visit %d with step %d\n", cur, step)
        for _, e := range graph.neighbors(cur) {
            if visited[e.to] { 
                continue
            }
            q = append(q, &State{e.to, step + 1})
            visited[e.to] = true
        }
    }
}

javascript

// BFS traversal of a graph structure, starting from node s and recording the
// number of steps (the number of edges from the start node s to the current node)
// each node maintains a State class to record the number of steps from s
class State {
    constructor(node, step) {
        // current node ID
        this.node = node;
        // number of steps from the start node s to the current node
        this.step = step;
    }
}

var bfs = function(graph, s) {
    var visited = new Array(graph.size()).fill(false);
    var q = [new State(s, 0)];
    visited[s] = true;
    while (q.length !== 0) {
        var state = q.shift();
        var cur = state.node;
        var step = state.step;
        console.log("visit " + cur + " with step " + step);
        var neighbors = graph.neighbors(cur);
        for (var i = 0; i < neighbors.length; i++) {
            var e = neighbors[i];
            if (visited[e.to]) { 
                continue;
            }
            q.push(new State(e.to, step + 1));
            visited[e.to] = true;
        }
    }
}

In this algorithm, we use State.step to record the least number of steps (edges) from the start to the current node, and use a visited array so each node is visited only once (enters and leaves the queue only once), to avoid loops.

In a weighted graph, the shortest path problem wants to find the smallest total weight from the start to each node. Because edges can have different weights, the least step count used above does not help and cannot give the path with the smallest total weight.

Here is the code for Dijkstra's algorithm. The differences are highlighted below:

Dijkstra Principles and Implementation

Dijkstra Algorithm Code

Key Differences Between Dijkstra and BFS

Complexity Analysis

Optimization for Point-to-Point Shortest Path

Summary