Dijkstra Algorithm Template and Applications

labuladongOriginalAbout 5002 words

Prerequisites

Before reading this article, you should first study:

Summary in One Sentence

The Dijkstra algorithm is used for finding the shortest path from a single source in a graph. Essentially, it is a specially modified BFS algorithm with two key modifications:

It uses a priority queue instead of a regular queue for BFS.
It includes a memoization technique to record the shortest path weights from the start node to each reachable node.

Before learning the Dijkstra shortest path algorithm, you need to understand the Basic Graph Structure and General Code Implementation. In the following explanation, I will use the general API of the Graph structure.

Additionally, you must comprehend the basic principles of BFS traversal in both DFS/BFS Traversal of Binary Trees and DFS/BFS Traversal of Graph Structures, as the Dijkstra algorithm is essentially a specially modified BFS algorithm.

When explaining the BFS traversal algorithm for binary trees and graph structures, I presented three different BFS approaches. If you have forgotten them, you might want to review them.

The third BFS approach is relatively more complex but the most flexible, as it introduces a State class, allowing each node to independently maintain additional information.

Here is the specific code:

java 🟢

// Level-order traversal of a multi-way tree
// Each node maintains its own State class to record depth and other information
class State {
    Node node;
    int depth;

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

void levelOrderTraverse(Node root) {
    if (root == null) {
        return;
    }
    Queue<State> q = new LinkedList<>();
    // Record the current level being traversed (root node is considered as level 1)
    q.offer(new State(root, 1));

    while (!q.isEmpty()) {
        State state = q.poll();
        Node cur = state.node;
        int depth = state.depth;
        // Visit the cur node and know its level
        System.out.println("depth = " + depth + ", val = " + cur.val);

        for (Node child : cur.children) {
            q.offer(new State(child, depth + 1));
        }
    }
}


// BFS traversal of a graph, starting from node s and recording the total weight of the path
// Each node maintains its own State class to record the total weight from s
class State {
    // Current node ID
    int node;
    // Total weight from the start node s to the current node
    int weight;

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


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 weight = state.weight;
        System.out.println("visit " + cur + " with path weight " + weight);
        for (Edge e : graph.neighbors(cur)) {
            if (!visited[e.to]) {
                q.offer(new State(e.to, weight + e.weight));
                visited[e.to] = true;
            }
        }
    }
}

cpp 🤖

// Level-order traversal of a multi-way tree
// Each node maintains its own State class to record depth and other information
class State {
public:
    Node* node;
    int depth;

    State(Node* node, int depth) : node(node), depth(depth) {}
};

void levelOrderTraverse(Node* root) {
    if (root == nullptr) {
        return;
    }
    queue<State> q;
    // Record the current level being traversed (root node is considered level 1)
    q.push(State(root, 1));

    while (!q.empty()) {
        State state = q.front();
        q.pop();
        Node* cur = state.node;
        int depth = state.depth;
        // Visit the cur node and also know its level
        cout << "depth = " << depth << ", val = " << cur->val << endl;

        for (Node* child : cur->children) {
            q.push(State(child, depth + 1));
        }
    }
}


// BFS traversal of a graph structure, starting from
// node s, and record the total weight of the path
// Each node maintains its own State class to record the total weight from s
class State {
public:
    // Current node ID
    int node;
    // Total weight from starting point s to the current node
    int weight;

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

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 weight = state.weight;
        cout << "visit " << cur << " with path weight " << weight << endl;
        for (const Edge& e : graph.neighbors(cur)) {
            if (!visited[e.to]) {
                q.push(State(e.to, weight + e.weight));
                visited[e.to] = true;
            }
        }
    }
}

python 🤖

# Level order traversal of a multi-way tree
# Each node maintains its own State class, recording depth and other information
class State:
    def __init__(self, node, depth):
        self.node = node
        self.depth = depth

def levelOrderTraverse(root):
    if root is None:
        return
    from collections import deque
    q = deque([State(root, 1)])
    while q:
        state = q.popleft()
        cur = state.node
        depth = state.depth
        # Visit the cur node while knowing its depth
        print(f"depth = {depth}, val = {cur.val}")
        
        for child in cur.children:
            q.append(State(child, depth + 1))


# BFS traversal of a graph structure, starting BFS from node s and recording the path weights
# Each node maintains its own State class, recording the weight from the starting node s
class State:
    def __init__(self, node, weight):
        # Current node ID
        self.node = node
        # Weight sum from start node s to the current node
        self.weight = weight


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
        weight = state.weight
        print(f"visit {cur} with path weight {weight}")
        for e in graph.neighbors(cur):
            if not visited[e.to]:
                q.append(State(e.to, weight + e.weight))
                visited[e.to] = True

go 🤖

// Level order traversal of a multi-way tree
// Each node maintains its own State class, recording depth and other information
type State struct {
    node  *Node
    depth int
}

func levelOrderTraverse(root *Node) {
    if root == nil {
        return
    }
    q := []*State{{root, 1}}
    for len(q) > 0 {
        state := q[0]
        q = q[1:]
        cur := state.node
        depth := state.depth
        // Visit the cur node, while knowing its depth level
        fmt.Printf("depth = %d, val = %d\n", depth, cur.val)

        for _, child := range cur.children {
            q = append(q, &State{child, depth + 1})
        }
    }
}

// BFS traversal of a graph structure, starting
// from node s and recording the sum of path weights
// Each node maintains its own State class, recording the sum of weights from s
type State struct {
    // Current node ID
    node   int
    // Sum of weights from the start node s to the current node
    weight 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
        weight := state.weight
        fmt.Printf("visit %d with path weight %d\n", cur, weight)
        for _, e := range graph.neighbors(cur) {
            if !visited[e.to] {
                q = append(q, &State{e.to, weight + e.weight})
                visited[e.to] = true
            }
        }
    }
}

javascript 🤖

// level order traversal of a multi-way tree
// each node maintains a State class to record depth and other information
class State {
    constructor(node, depth) {
        this.node = node;
        this.depth = depth;
    }
}

var levelOrderTraverse = function(root) {
    if (root === null) {
        return;
    }
    var q = [new State(root, 1)];
    while (q.length !== 0) {
        var state = q.shift();
        var cur = state.node;
        var depth = state.depth;
        // visit the cur node and know its level
        console.log("depth = " + depth + ", val = " + cur.val);

        for (var i = 0; i < cur.children.length; i++) {
            var child = cur.children[i];
            q.push(new State(child, depth + 1));
        }
    }
}


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

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 weight = state.weight;
        console.log("visit " + cur + " with path weight " + weight);
        var neighbors = graph.neighbors(cur);
        for (var i = 0; i < neighbors.length; i++) {
            var e = neighbors[i];
            if (!visited[e.to]) {
                q.push(new State(e.to, weight + e.weight));
                visited[e.to] = true;
            }
        }
    }
}

This approach might seem redundant for tree structures, but it is highly useful for weighted graphs.

The Dijkstra algorithm we are about to implement is an improvement based on this method. Each node needs to record the shortest path weight sum from the starting point to itself. By using a priority queue, a data structure that allows dynamic sorting, you can efficiently compute the shortest path.

Next, let's introduce the general code implementation of the Dijkstra algorithm.

Dijkstra Algorithm Template and Applications

Dijkstra Function Signature

`State` Class

`distTo` Records the Shortest Path

Code Implementation

Time Complexity Analysis