So I spent some time afternoon to understand the idea behind Dijkstra. On this post, I wish to focus on the graph theoretical language and idea behind the algorithm rather than its application. I will cover the idea of crossing subsets and use path notations for graphs to formalize our idea.
Suppose a graph \(G\) is give. Choose an initial point \(u_0\) and some set \(S\) that includes \(u_0\). Our interest will be the minimum distance that is required to leave the set \(S\) through a graph traversal.
For housekeeping, we define a weight function and distance.
Definition 1. A weight function associated to simple graph \(G\) is a mapping \(w:E(G)\rightarrow \mathbb R^+\) that maps an edge of the graph to some strictly positive real number. For convenience, if two vertices \(u, v\) are not connected by an edge, we set \(w(uv) = \infty\).
Definition 2. A distance between two vertices \(u, v\) is the denoted by the minimum of all the weight sum along all the paths that connect \(u, v\), i.e.
\[d(u, v) \ = \ \min_p \{ \sum_{e \in E(p)} w(e)\}\]
where path \(p\) has its origin in \(u\) and terminus in \(v\). Also, the distance between a set and a graph can be measured by a similar minimization. Set path \(p\) to have the same origin \(u\), but this time, allow the terminus to run through any point in \(w \in S\). Then,
\[d(u, S) \ = \ \min_p \{\sum_{e \in E(p)} w(e)\}\]
We present two propositions that each describes how to compute a distance between a vertex and a set, and how to derive a single distance relation between two vertices from the set distance.
Proposition 1.
\[d(u_0, S) \ = \ \min_{u\in S v \notin S} d(u_0, u) + w(uv)\]
proof. Argue by construction, and assume that there exists a path that has a shorter total weight compared the sum of the weight and distance. It is possible to choose a shorter subpath \(p’\) that passes entirely through set \(S\) other than some terminus \(v’\in S^C\). Listing out the vertices of \(p’\), we get
\[p \ = \ \dots u_0 \dots u’ v’\]
and by construction,
\[d(u_0, u) + w(uv) \ \geq d(u_0, u’) + w(u’v’)\]
which contradicts the minimality of the choice \(u \in S, v\notin S\) in the first place. □
Proposition 2. If it is the case that \(d(u_0, S) = d(u_0, u) + w(uv)\) for some \(u\in S, v\notin S\), then the distance between verticies \(u_0, v\) is prescribed by
\[d(u_0, v) \ = \ d(u_0, u) + w(u, v).\]
proof. Argue by the same argument as above. For the sake of contradiction, choose a path that sees witness to the claim that \(d(u_0, v) \ < \ d(u_0, u) + w(u, v)\) and take a subpath \(p’=u_0\dots u’v’\) such that all vertices \(u_0, \dots, u’ \in S\) and \(v’\notin S\). The minimality of the initial choice \(u, v\) for the distance function \(d(u_0, S\) is contradicted. □
An important technique of graph theory is to associate a quantity to a set. The minimal or maximal choice is contradicted by manipulating the set. This method is more powerful than looking at individual vertices or edges, since graphs are finite and associated quantities must attain the minimum for some arbitrary choice.
From the two propositions, it is straightforward to prove the following algorithm
Dijkstra’s algorithm.
Given a simple graph \(G\) and a strictly positive weight function \(w:E(G)\rightarrow \mathbb R^+\), the following process can be used to find the minimum distance between a set initial point \(u_0\) and all \(w \in E(G)\).
- Set \(d(u_0, u_0) = 0\) and \(S_0 = \{u_0\}\).
- Compute \(d(u_0, S_n^C) = d(u_0, u) +w(u, v)\) by iterating over all the edges \(uv \in E(G)\) such that \(u \in S_n, v\notin S_n\) and finding the minimizer. (Prop 1)
- Induct \(v\) into the \(S\) set, i.e. \[S_{n+1} \ = \ S_n\cup\{v\}\]
- Set \(d(u_0, v) = d(u_0, u) + w(uv)\). (Prop 2)
Eventually, the set \(S_n\) will cover all vertices in \(G\) and the algorithm will terminate.
Leave a Reply