Shortest Paths

Section 6.3 Shortest Paths

Erdős Number.

The mathematician Paul Erdős is renowned for having been one of the most prolific mathematicians of the 20th century, as well as one of the most social: he wrote papers with more than 500 collaborators over his career. Due to his frequent collaborations, one of his coauthors assigned to Paul an “Erdős number” of 0, for being Paul Erdős. Each of Erdős’s coauthors were assigned an Erdős number of 1. Their coauthors who did not coauthor with Erdős were assigned an Erdős number of 2, and so on.

This builds a rooted collaboration graph: a graph whose vertices are mathematicians and edges are coauthorship on a paper, with a special root vertex designated as Paul Erdős. The distance in this graph is the length of a shortest path between vertices. The question then is how to determine a shortest path.

While this problem is described in terms of something lighthearted, shortest paths are important in other mediums as well. In fact, one of the largest graphs under current study is the Facebook graph! If a transmission of a message in a network is more likely to have errors introduced with each subsequent connection traversed, it is important to minimize the number of transmissions. With a little creativity, the shortest path problem can be applied to hyperspace routing for a particular type of fictional faster-than-light travel.

Subsection 6.3.1 Dijkstra’s Algorithm

In 1956, Dutch computer scientist Edsger Dijkstra developed an algorithm for solving this problem. His solution, now known as Dijkstra’s algorithm, is both elegant and simple. A root vertex is specified as having distance 0; its neighbors have distance 1. The neighbors of those vertices with distance 1 are next specified to have distance 2, unless they previously had distance 0; and so on. Those vertices which cannot be reached by a path from the root have distance \(\infty\text{.}\)

Algorithm 6.3.1. Dijkstra’s Shortest Path Algorithm.

Let \(\Gamma=(V,E)\) be a graph, and let \(x\) be a particular vertex in \(V\text{.}\) We will define \(\dist{\Gamma}{x}{v}\) to be the currently known distance from \(x\) to \(v\text{,}\) and \(V'=\set{}\) to be an initially empty set. For each \(v\in V\setminus\set{x}\text{,}\) we define \(p(v)\) to be the predecessor of \(v\) in a shortest path from \(x\text{.}\)

Mark \(\dist{\Gamma}{x}{x}=0\) and \(\dist{\Gamma}{x}{v}=\infty\) for every \(v\in V\setminus\set{x}\text{.}\)
While \(V\neq V'\text{,}\) do the following:
1. Let \(u\) be any vertex in
  
  \begin{equation*} \set{u\in V\setminus V': \dist(u)=\min\set{\dist{\Gamma}{x}{v}:v\in V\setminus V'}}\text{.} \end{equation*}
2. Add \(u\) to \(V'\text{.}\)
3. For each neighbor \(v\) of \(u\text{,}\) if \(\dist{\Gamma}{x}{v}>\dist(u)+1\text{,}\) set \(\dist{\Gamma}{x}{v}=\dist(u)+1\text{,}\) and set \(p(v)=u\text{.}\)
Return the triple \((v,\dist{\Gamma}{x}{v}, p(v))\) for each \(v\in V\text{.}\)

In fact, Dijkstra’s algorithm produces what is called a breadth-first traversal of \(\Gamma\) from the root vertex \(x\text{.}\) For each vertex \(v\) in the same component of \(\Gamma\) as \(v_0\text{,}\) there is a finite sequence of predecessors which can be followed backwards from \(v\) to \(x\text{;}\) for vertices in other components, no such predecessor exists and the distance \(\dist(x,v)\) is infinite. We’ll illustrate the algorithm with the example of a graph with two components, one of which is a single isolated vertex.

Figure 6.3.2. A graph \(\Gamma\) with two components: the vertex \(v_{16}\) is isolated from all other vertices.

Subsubsection 6.3.1.1 A full example of Dijkstra’s algorithm

Consider the graph \(\Gamma=(V,E)\) with vertex set \(V=\set{1,2,\ldots,16}\) and edge set

\begin{align*} E \amp = \left\{(1, 2), (1, 14), (2, 5), (2, 7), (2, 15), (3, 4), (3, 6), (3, 7), (4, 8), (4, 11), (4, 15), \right.\\ \amp ~\left.(5, 11), (6, 8), (6, 9), (6, 11), (7, 11), (8, 9), (8, 12), (8, 14), (9, 10), (9, 15),\right.\\ \amp ~\left.(10, 11), (10, 12), (10, 13), (11, 13), (12, 14), (12, 15), (13, 14), (13, 15), (14, 15)\right\}. \end{align*}

This graph is depicted in Figure 6.3.2. If we designate the root vertex to be \(x=v_1\text{,}\) we can begin the process. The iterations are explained briefly, and all steps are tabulated below in Table 6.3.3. Since \(x=v_1\text{,}\) we set

\begin{equation*} \dist{\Gamma}{x}{v} = \begin{cases}\infty \amp v\neq v_1 \\0 \amp v=v_1 \end{cases} \end{equation*}

and \(p(v)\) takes no values. As the only unvisited vertex at finite distance from \(x\text{,}\) we mark \(v_1\) as visited by putting \(V'=\set{v_1}\text{.}\) Looking at the neighbors of \(v_1\text{,}\) we see that \(N(v_1) = \set{v_2, v_{14}}\text{;}\) since the distance to both is currently infinite, we redefine \(d\) and \(p\) as follows:

\begin{align*} \dist{\Gamma}{x}{v} \amp = \begin{cases}0 \amp v=v_1 \\ 1 \amp v\in \set{v_2,v_{14}} \\ \infty \amp \text{ otherwise } \end{cases} \amp p(v) \amp = 1\text{ for } v\in\set{v_2, v_{14}}. \end{align*}

Since \(2\lt 14\text{,}\) we choose next to visit \(v_2\text{;}\) hence \(V'=\set{v_1,v_2}\) and we observe that the as-yet-unvisited neighbors of \(v_2\) are \(v_5\text{,}\) \(v_7\text{,}\) and \(v_{15}\text{.}\) We again update \(d\) and \(p\text{:}\)

\begin{align*} \dist{\Gamma}{x}{v} \amp = \begin{cases}0 \amp v=v_1 \\ 1 \amp v\in \set{v_2,v_{14}} \\ 2 \amp v\in \set{v_5, v_7, v_{15}} \\ \infty \amp \text{ otherwise } \end{cases} \amp p(v) \amp = \begin{cases}1 \amp v\in\set{v_2, v_{14}} \\ 2 \amp v\in\set{v_5, v_7, v_{15}} \end{cases} \end{align*}

Proceeding in this manner, we will visit vertices \(v_{14}\text{,}\) \(v_5\text{,}\) \(v_7\text{,}\) \(v_{15}\text{,}\) \(v_8\text{,}\) and \(v_{12}\) before something strange happens: every vertex will have been visited or ``seen" on its shortest path, except for \(v_{16}\text{.}\) While \(v_{16}\) will eventually be added to \(V'\text{,}\) it will never be seen as a neighbor of another vertex, and will never be assigned a predecessor.

Table 6.3.3. Iterations of Dijkstra’s algorithm on the graph \(\Gamma\) from Figure 6.3.2.

	Current			Updating Vertices
Step	Vertex	Distance	Predecessor	\(\set{v_j:j\in J}\)	\((\dist{\Gamma}{x}{v}, p(v))\)
0	1	0	None	[2, 14]	(1, 1)
1	2	1	1	[5, 7, 15]	(2, 2)
2	14	1	1	[8, 12, 13]	(2, 14)
3	5	2	2	[11]	(3, 5)
4	7	2	2	[3]	(3, 7)
5	15	2	2	[4, 9]	(3, 15)
6	8	2	14	[6]	(3, 8)
7	12	2	14	[10]	(3, 12)
8	13	2	14	[ ]	(3, 13)
9	11	3	5	[ ]	(4, 11)
10	3	3	7	[ ]	(4, 3)
11	4	3	15	[ ]	(4, 4)
12	9	3	15	[ ]	(4, 9)
13	6	3	8	[ ]	(4, 6)
14	10	3	12	[ ]	(4, 10)
15	16	\(\infty\)	None	[ ]	(\(\infty\text{,}\) 16)

Are there other ways to find shortest paths? Of course. The beauty of using Dijkstra’s algorithm is that when you first encounter a vertex, you’re already recording its shortest path. It will never be the case that this algorithm encounters a vertex at some large distance and then updates it to a smaller distance.

Prev Top Next