Finding the best route between two cities, given a complicated road network; or transmitting a message between two computers along a network of hundreds of computers, are all classified as the shortest path problem.

# Dijkstra's Algorithm

Dijkstra's algorithm was designed to find the shortest path, in a weighted graph, between two points $$a$$ and $$z$$. This is done by initially labeling each vertex other than $$a$$ with $$\infty$$, labeling $$a$$ with $$0$$, and then modifying the labels as shortest paths within the graph were constructed. These labels are temporary; they become permanent when it becomes apparent that a label could never become smaller.

If this process is continued until every vertex in a connected, weighted graph has a permanent label, then the lengths of the shortest paths from $$a$$ to each other vertex of the graph are determined.

As an example, we use this algorithm to find the shortest path between $$a$$ and $$z$$ in the graph below:

1. The only paths starting at $$a$$ that contain no vertex other than $$a$$ are formed by adding an edge that has $$a$$ as one endpoint. These paths have only one edge. They are $$a,b$$ of length $$4$$ and $$a,d$$ of length $$2$$. It follows that $$d$$ is the closest vertex to $$a$$ with length $$2$$.
2. The second closet vertex can be found by examining all paths that begin with the shortest path from $$a$$ to a vertex in the set $$\{a,d\}$$, followed by an edge that has one endpoint in $$\{a,d\}$$ and its other endpoint not in this set. There are two such paths to consider, $$a,d,e$$ of length $$7$$ and $$a,b$$ of length $$4$$. Hence, the second closet vertex to $$a$$ is $$b$$ with length $$4$$.
3. Examine $$\{a,d,b\}$$. There are three such paths, $$a,b,c$$ of length $$7$$, $$a,b,e$$ of length $$7$$, and $$a,d,e$$ of length $$5$$. We then choose $$a,d,e$$ of length $$5$$.
4. Examine $$\{a,d,b,e\}$$. There are two such paths, $$a,b,c,$$ of length $$7$$ and $$a,d,e,z$$ of length $$6$$. So the shortest path from $$a$$ to $$z$$ is $$a,d,e,z$$ with length $$6$$.

We can repeat this process with any other point besides $$a$$ as the initial point, and eventually all possible shortest paths between any two points of the graph can be determined. But it is not so efficient as a process to find all shortest paths.

# Hedetniemi's Algorithm

The algorithm constructed here is based on a new way to compute powers of matrices, which we will call the Hedetniemi matrix sum. Suppose we begin with a connected, weighted graph with vertices $$v_1,\dots,v_n$$. With this graph we associate the $$n\times n$$ "adjacency" matrix $$A =[a_{ij}]$$ defined as follows: \displaylines{\begin{aligned} a_{ij}= \begin{cases} 0 &\text{if }i=j \\ x &\text{if i\neq j and there is an edge of weight x between i and j}\\ \infty &\text{otherwise} \end{cases} \end{aligned} } For example, the graph above have the adjacency matrix $$A$$, when $$a,b,c,d,e,z$$ are denoted by $$v_1,v_2,v_3,v_4,v_5,v_6$$ respectively. $\displaylines{A=\begin{pmatrix} 0 & 4 & \infty & 2 & \infty & \infty \\ 4 & 0 & 3 & \infty & 3 & \infty \\ \infty & 3 & 0 & \infty & \infty & 2 \\ 2 & \infty & \infty & 0 & 3 & \infty \\ \infty & 3 & \infty & 3 & 0 & 1 \\ \infty & \infty & 2 & \infty & 1 & 0 \end{pmatrix} }$ We now introduce an operation on matrices called the Hedetniemi matrix sum, denoted by $$\dashv\vdash$$. Let $$A$$ be an $$m\times n$$ matrix and $$B$$ an $$n\times p$$ matrix. Then the Hedetniemi matrix sum is the $$m\times p$$ matrix $$C=A\dashv\vdash B$$, whose $$(i,j)$$th entry is $\displaylines{c_{ij}=\min\{a_{i1}+b_{1j},a_{i2}+b_{2j},\dots,a_{1n}+b_{nj}\} }$ Then $\displaylines{A^2=\begin{pmatrix} 0 & 4 & 7 & 2 & 5 & \infty \\ 4 & 0 & 3 & 6 & 4 & 5 \\ 7 & 3 & 0 & \infty & 3 & 2 \\ 2 & 6 & \infty & 0 & 3 & 4 \\ 5 & 3 & 3 & 3 & 0 & 1 \\ \infty & 4 & 2 & 4 & 1 & 0 \end{pmatrix} }$ Look at a typical computation involved in finding $$A^2=[a_{ij}^{(2)}]$$: \displaylines{\begin{aligned} a_{13}^{(2)}&=\min\{0+\infty, 4+3, \infty+0, 2+\infty, \infty+\infty, \infty+2 \} \\ &=7 \end{aligned} } Notice that the value $$7$$ is the sum of $$4$$, the shortest path of length $$1$$ from $$v_1$$ to $$v_2$$, and $$3$$, the length of the edge between $$v_2$$ and $$v_3$$. Thus $$a_{13}^{(2)}$$ represents the length of the shortest path of two ore fewer edges from $$v_1$$ to $$v_3$$. So $$A^2$$ represents the lengths of all shortest paths with two or fewer edges between any two vertices. Similarly, $$A^3$$ represents the lengths of all shortest paths of three or fewer edges, and so on. Since, in a connected, weighted graph with $$n$$ vertices, there can be at most $$n − 1$$ edges in the shortest path between two vertices, the following theorem has been proved.

Theorem 1 In a connected, weighted graph with $$n$$ vertices, the $$(i,j)$$th entry of the Hedetniemi matrix $$A^{n-1}$$ is the length of the shortest path between $$v_i$$ and $$v_j$$.

In the graph above, with $$6$$ vertices, we have $\displaylines{A^5=\begin{pmatrix} 0 & 4 & 7 & 2 & 5 & 6 \\ 4 & 0 & 3 & 6 & 4 & 5 \\ 7 & 3 & 0 & 6 & 3 & 2 \\ 2 & 6 & 6 & 0 & 3 & 4 \\ 5 & 3 & 3 & 3 & 0 & 1 \\ 6 & 4 & 2 & 4 & 1 & 0 \end{pmatrix} }$ Therefore, the shortest path from $$v_1$$ to $$v_6$$ is of length $$6$$.

An interesting fact about this example is that $$A^3=A^5$$. This happens because in this graph, no shortest path has more than $$3$$ edges. So, no improvements in length can occur after $$3$$ iterations. This gives us the following theorem.

Theorem 2 For a connected, weighted graph with $$n$$ vertices, if the Hedetniemi matrix $$A^k\ne A^{k-1}$$, but $$A^k=A^{k+1}$$, then $$A^k$$ represents the set of lengths of shortest paths, and no shortest path contains more than $$k$$ edges.

# Shortest Path Calculations

To compute the actual shortest path from one point to another, it is necessary to have not only the final matrix, but also its predecessor and $$A$$ itself. We want to find the shortest path from $$v_1$$ to $$v_6$$. Now $\displaylines{a_{16}^{(3)}=a_{1k}^{(2)}\dashv\vdash a_{k6} }$ for some $$k$$. The entries $$a_{1k}^{(2)}$$ form the row vector $\displaylines{(0,4,7,2,5,\infty) }$ and the entries $$a_{k6}$$ form the column vector $\displaylines{(\infty,\infty,2,\infty,1,0) }$ Since the only way in which $$6$$ arises is as the sum $$5+1$$ when $$k=5$$, the shortest path ends with an edge of length $$1$$ from $$v_5$$ to $$v_6$$, following a path with $$2$$ or fewer edges from $$v_1$$ to $$v_5$$.

Now we can look for the previous edge ending at $$v_5$$. Note that $$a_{15}^{(2)}=5$$. The entries $$a_{k5}$$ form the column vector $\displaylines{(\infty,3,\infty,3,0,1) }$ This time $$5$$ arises, when $$k=4$$, as $$2+3$$, so there is an edge of length $$2$$ from $$v_1$$ to $$v_4$$. So the shortest path from $$v_1$$ to $$v_6$$ is $$v_1, v_4, v_5, v_6$$ (the edges of lengths $$2, 3, 1$$).

Thus, the Hedetniemi method provides a graphical interpretation at each stage of the computation, and the matrices can be used to retrieve the paths themselves.

Reference: