# Trivial clarification with the analysis of the Dijkstra Algorithm as dealt with in Keneth Rosen’s “Discrete Mathematics and its Application”

I was going through the text, “Discrete Mathematics and its Application” by Kenneth Rosen where I came across the analysis of the Dijkstra Algorithm and felt that the values at some places of the analysis are not quite appropriate. The main motive of my question is not the analysis of the Dijkstra Algorithm in general( a better version and more clearer version exists in the CLRS text) but my main motive is analysis of the algorithm acurately as far as the mathematics is concerned, considering the below algorithm as just an unknown algorithm whose analysis is required to be done. I just want to check my progress by the fact that whether the thing which I pointed out as being weird, is actually weird or not.

Lets move on to the question. Below is the algorithm in the text.

ALGORITHM: Dijkstra’s Algorithm.

``procedure Dijkstra(G: weighted connected simple graph, with all weights positive)        {G has vertices a = v, ... ,v[n] = z and weights w(v[j], v[j])      where w(v[j], v[j]) = ∞ if {v[i],v[j]) is not an edge in G}      for i: = 1 to n         L(v[i]) := ∞      L(a) := 0      S:=∅      {the labels are now initialized so that the label of a is 0 and all          other labels are ∞, and S is the empty set}       while z ∉ S          u := a vertex not in S with L(u) minimal          S:= S ∪ {u}          for all vertices v not in S              if L(u) + w(u, v) < L(v) then                  L(v) := L(u) + w(u, v)              {this adds a vertex to S with minimal label and updates the labels of vertices not in S}            return L(z)  {L(z) = length of a shortest path from a to z} ``

The following is the analysis which they used:

We can now estimate the computational complexity of Dijkstra’s algorithm (in terms of additions and comparisons). The algorithm uses no more than $$n − 1$$ iterations where $$n$$ is the number of vertices in the graph, because one vertex is added to the distinguished set at each iteration. We are done if we can estimate the number of operations used for each iteration. We can identify the vertex not in S in the $$k$$th iteration with the smallest label using no more than $$n − 1$$ comparisons. Then we use an addition and a comparison to update the label of each vertex not in S in the $$k$$th iteration . It follows that no more than $$2(n − 1)$$ operations are used at each iteration, because there are no more than $$n − 1$$ labels to update at each iteration.

The algorithm uses no more than $$n − 1$$ iterations where $$n$$ is the number of vertices in the graph, because one vertex is added to the distinguished set at each iteration., What I feel is that it shall be $$n$$ iterations and not $$n$$ as in the very first iteration the vertex $$a$$ is included in the set $$S$$ and the process continues till $$z$$ is inserted into the set $$S$$ and $$z$$ may be the last vertex in the ordering i.e.$$v_n$$.

The rest statements are fine I hope.

Posted on Categories proxies