Question

Suppose we want to run Dijkstra’s algorithm on a graph whose edge weights are integers in the range $0,1,........,W$, where $W$is a relatively small number.
(a) Show how Dijkstra’s algorithm can be made to run in time

$O\left(W\left|V\right|+\left|E\right|\right)$

(b) Show an alternative implementation that takes time just .

$O\left(\left(\left|V\right|+\left|E\right|\right)logW\right)$

Short answer

a)Dijkstra’s algorithm can be made to run in time$O\left(W\left|V\right|+\left|E\right|\right)$ is proved.

b)Dijkstra’sAlgorithm performs$TC=O\left[\left(\left|V\right|+\left|E\right|\right)logW\right]$ time complexity is

Step-by-step solution

Step 1:Dijkstra’s algorithm.

Dijkstra algorithm is an application of single source shortest path.Dijkstra’s algorithm also known as SPF algorithm and is an algorithm for finding the shortest paths between the vertices in a graph. It returns a search tree for all the paths the given node can take. An acyclic graph is a directed graph that has no cycles. Its operation is performed in the minheap.

Step 2: Dijkstra’s algorithm can be made to run in time O(W|V|+|E|)a).

Let’s an example for finding the time complexity of the graph. A graph whose edge weights are integers in the range $0,1,\mathrm{........},W$, where $W$is a relatively small number.The graph $G(V,W)$where $V$are the vertices and $W$are the edges. In which Dijkstra algorithm for finding the shortest paths between the vertices in a graph.Evaluate single source shortest path just select any vertex and again select the next vertex as a minimum weight. After applying this process on all the vertex. Add the edges and vertex of each steps. The time complexity can be evaluated.

Fig: Weighted Graph.

By these steps after adding the $V$as vertices and $W$as edgesHence its complexity is:.$O\left(W\left|V\right|+\left|E\right|\right)$

Step 3: Algorithm performs TC=O[(|V|+|E|)logW] time complexity.

b)

Time complexity for the graph $G(V,W)$where $V$are the vertices and$W$are the edges. The formula for minheap and adjacency list which are used as a data structure. For finding this just take a scenario in which Dijkstra algorithm forfinding the shortest paths between the vertices in a graph.the vertex$A$is the source vertex. now take a minheap as a data structure for evaluate single source shortest path between the source and the destination. From$A$the distance of is zero and take the distance of vertex from each and every vertex is infinity.Now take$A$as the first vertex and evaluate the weight towards each vertex.And choose the next vertex from the vertices which have minimum weight and select that node as the second vertex.Then again evaluate the distance of it from every vertex and as get the minimum weight of the node and consider it as the main node.Through this the series of vertex are arises.where$V$are the vertices and$W$are the edges.

Now the time complexity is given as:

$\begin{array}{l}TC=V+VlogV+E+ElogW\\ TC=VlogV+ElogW\\ TC=O\left[(V+E)logW\right]\end{array}$

For finding the shortest path adjacent list and minheap both may use. And the mode value represents here the vertex and the edges may oy may not be positive or negative. It works for both when the weighted graph has their edge is of positive or it may be negative weighted graph.

The time complexity is $TC=O\left[\left(\left|V\right|+\left|E\right|\right)log\left|W\right|\right]$.