Dijkstra Principles and Implementation
Prerequisites
Before reading this article, you need to learn:
Summary
Dijkstra's algorithm is used to find the shortest path from a single source 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 be used on graphs with no negative weight edges.
There are only two differences between Dijkstra's algorithm and the standard BFS algorithm:
The standard BFS uses a normal queue, while Dijkstra uses a priority queue. This lets nodes closer to the start be processed first (this is the greedy idea).
The standard BFS uses a
visitedarray to record visited nodes and avoid loops. Dijkstra uses adistToarray to avoid loops and also record the shortest distance from the start to each node.
In the article Overview of Shortest Path Algorithms in Graphs, we already talked about the shortest path problem in graphs, the difference between single-source and multi-source shortest paths, issues with negative weight edges, and several classic shortest path algorithms including Dijkstra. This article will cover:
How to get Dijkstra's algorithm code by changing the standard Graph BFS Traversal Algorithm.
A detailed explanation of how Dijkstra's algorithm works and why it is correct.
The point-to-point shortest path problem is a special case of the single-source shortest path. We will show how to change the standard Dijkstra code a bit to make it faster for this.
Once you learn these, you can try the problems in Dijkstra Algorithm Practice Problems. In Dijkstra Algorithm Advanced, we will update the code to solve more complex shortest path problems.
This article will use the graph interface we defined in Graph Basics and General Implementation. Please read that first to understand how graphs are stored and how the interface works.
Let's get started.
Dijkstra Algorithm Code
We'll start with the code, because Dijkstra's algorithm is just a small change from standard BFS. Let's see what is changed, then discuss why it is correct.
In Graph BFS Traversal Algorithm, we showed three ways to write BFS. The third way fits Dijkstra well because we need to keep track of the shortest path from the start to each node we visit.
Here is the standard graph BFS algorithm for comparison:
// 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;
}
}
}// 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;
}
}
}# 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
}
}
}// 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 minimum number of steps (edges) from the start to the current node, and a visited array to make sure each node is visited only once, so the algorithm does not loop forever.
In a weighted graph, the shortest path problem is about finding the minimum total weight from the start to every other node. Since each edge can have a different weight, counting the number of steps (edges) no longer works. It won't give us the path with the smallest weight sum.
Here is the Dijkstra algorithm code, with the changes highlighted: