## 4.2 Dijkstra's Algorithm for Single-Source Shortest Paths In [Section 3.2](LiB0031.html#350), we developed a θ(*n*3) algorithm for determining the shortest paths from each vertex to all other vertices in a weighted, directed graph. If we wanted to know only the shortest paths from one paticular vertex to all the others, that algorithm would be overkill. Next we will use the greedy approach to develop a θ(*n*2) algorithm for this problem (called the Single Source Shortest Paths problem). This algorithm is due to Dijkstra (1959). We present the algorithm, assuming that there is a path from the vertex of interest to each of the other vertices. It is a simple modification to handle the case where this is not so. This algorithm is similar to Prim's algorithm for the Minimum Spanning Tree problem. We initialize a set *Y* to contain only the vertex whose shortest paths are to be determined. For focus, we say that the vertex is *v*1. We initialize a set *F* of edges to being empty. First we choose a vertex *v* that is nearest to *v*1, add it to *Y*, and add the edge <*v*1, *v*> to *F*. (By < *v*1, *v* > we mean the directed edge from *v*1 to *v*.) That edge is clearly a shortest path from *v*1 to *v*. Next we check the paths from *v*1 to the vertices in *V* - *Y* that allow only vertices in *Y* as intermediate vertices. A shortest of these paths is a shortest path (this needs to be proven). The vertex at the end of such a path is added to *Y*, and the edge (on the path) that touches that vertex is added to *F*. This procedure is continued until *Y* equals *V*, the set of all vertices. At this point, *F* contains the edges in shortest paths. The following is a high-level algorithm for this apporoach. ``` Y = {v1}; F = Ø while (the instance is not solved) { select a vertex v from V - Y, that has a // selection shortest path from v1, using only vertices in // procedure and in Y as intermediates; // feasibility check add the new vertex v to Y; add the edge (on the shortest path) that touches v to F; if (Y == V) the instance is solved; // solution check } ``` [Figure 4.8](#ch04fig08) illustrates Dijkstra's algorithm. As was the case for Prim's algorithm, the high-level algorithm works only for a human solving an instance by inspection on a small graph. Next we give a detailed algorithm. For this algorithm, the weighted graph is represented by a two-dimensional array exactly as was done in [Section 3.2](LiB0031.html#350). This algorithm is very similar to [Algorithm 4.1](LiB0033.html#378) (Prim's). The difference is that instead of the arrays *nearest* and *distance*, we have arrays *touch* and *length*, where for *i* = 2, …, *n*, [](fig4-8_0.jpg) Figure 4.8: A weighted, directed graph (in upper-left corner) and the steps in Dijkstra's algorithm for that graph. The vertices in *Y* and the edges in *F* are shaded in color at each step. *touch\[i\]* = index of vertex *v* in *Y* such that the edge <*v*, *vi*> is the last edge on the current shortest path from *v*1 to *vi* using only vertices in *Y* as intermediates. *length\[i\]* = length of the current shortest path from *v*1 to *v*i using only vertices in *Y* as intermediates. The algorithm follows. Algorithm 4.3: Dijkstra's Algorithm****Problem: Determine the shortest paths from *v*1 to all other vertices in a weighted, directed graph. Inputs: integer *n* ≥ 2, and a connected, weighted, directed graph containing *n* vertices. The graph is represented by a two-dimensional array *W*, which has both its rows and columns indexed from 1 to *n*, where *W\[i\]\[j\]* is the weight on the edge from the *i*th vertex to the *j*th vertex. Outputs: set of edges *F* containing edges in shortest paths. ``` void dijkstra (int n, const number W[][], set_of_edges&F) { index i, unear; edge e; index touch [2 .. n]; number length [2 .. n]; F = Ø; for (i = 2; i<= n; i++){ // For all vertices, initialize v1touch [i] = 1; // to be the last vertex on the length [i] = W[1] [i]; // current shortest path from } // v1, and initialize length of // that path to be the weight // on the edge from v1. repeat (n - 1 times){ // Add all n - 1 vertices to Y. min = ∞; for (i = 2; i < = n; i++) // Check each vertex for if ( 0 ≤ length [i] < min) { // having shortest path. min = length [i]; unear = i; } e = edge from vertex indexed by touch [vnear] to vertex indexed by vnear; add e to F; for (i = 2; i < = n; i++) if (length [vnear] + W[vnear] [i] < length [i]){ length[i] = length[vnear] + W[vnear][i]; touch[i] = vnear; // For each vertex not in Y, } // update its shortest path. length[vnear] = -1; // Add vertex indexed by vnear } // to Y. } ``` **** Because we are assuming that there is a path from *v*1 to every other vertex, the variable *vnear* has a new value in each iteration of the **repeat** loop. If this were not the case, the algorithm, as written, would end up adding the last edge over and over until *n* - 1 iterations of the **repeat** loop were completed. [Algorithm 4.3](#ch04ex08) determines only the edges in the shortest paths. It does not produce the lengths of those paths. These lengths could be obtained from the edges. Alternatively, a simple modification of the algorithm would enable it to compute the lengths and store them in an array as well. The control in [Algorithm 4.3](#ch04ex08) is identical to that in [Algorithm 4.1](LiB0033.html#378). Therefore, from the analysis of that [Algorithm 4.1](LiB0033.html#378), we know for [Algorithm 4.3](#ch04ex08) that  Although we do not do it here, it is possible to prove that [Algorithm 4.3](#ch04ex08) always produces shortest paths. The proof uses an induction argument similar to the one used to prove that Prim's algorithm ([Algorithm 4.1](LiB0033.html#378)) always produces a minimum spanning tree. As is the case for Prim's algorithm, Dijkstra's algorithm can be implemented using a heap or a Fibonacci heap. The heap implementation is θ (*m* lg *n*), and the Fibonacci heap implementation is θ(*m + n* lg *n*), where *m* is the number of edges. See Fredman and Tarjan (1987) for this latter implementation.