91Ó°ÊÓ

Perform Dijkstra’s algorithm and Depth First Search.

Dijkstra algorithm is an application of a single source shortest path.

Dijkstra’s algorithm also known as the 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.

Depth First Search (DFS) is an application of graph traversal. It traverses the node downwards and uses the stack as a data structure through this it traverses all vertices in the downward direction one by one.

Some properties ofdepth-first search are as follows:

1. Using DFT we can verify that the graph is connected or not it means it detects the cycle present in the graph or not.
2. We can find out the number of connected components by usingdepth-first search.
3. Here we are using stack as a data structure.

The time complexity of list is $\mathrm{O}\left(\mathrm{V}+\mathrm{E}\right)$

The time complexity of matrix is$\mathrm{O}\left({\mathrm{V}}^2\right)$

It contains various edge they aretree edge, forward edge, back edge, or cross edge all the edges are explain below:

Tree edge: The graph obtained by traversing while using depth first search is called its tree edge.

Forward edge: the edge {u , v} where u is descendant and it is not part of depth first search is called forward edge.

Back edge: the edge {u , v} where u is ancestor and it is not part of depth first search is called back edge.

(a)

For finding the feasible route or the shortest route from s to t. Where these are the cities and as given in the question its length in miles, le. And we want to get from city s to city t. There’s one problem that is:

The car can only hold enough gas to cover L miles and there are gas stations in each city, but not between cities. Therefore, in this case first find out the shortest path between these two cities by using Dijkstra 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. and after that find out the sequence of cities which consider as a vertex and the distance between them is consider as the edge which may or may not be weighted. And here by using min heap or stack as a data structure the number of vertices as cities are stored in it.

After that apply depth first search It traverses the node downwards and uses the stack as a data structure through this it traverses all vertices in downward direction one by one.

Here the following steps are as follows:

1). Let’s Iteratethroughalltheedgesinthegraph.

2).Checkiftheweightofeveryedgeislessthanthegivenmiles.

3). Ifthereareedgesthatareweightedmorethan,removetheedge.

Otherwise,moveontothenextone.

4). After completing this step nowperformdepth first searchtogetfromcitystocityt

(b)

1). Perform Dijkstra’s algorithm on the graph from s to t by using the returned tree.

2). Find the shortest path from s to t using DFS

while noting the weights of the edges that make up the path.

3). Then return the largest weighted edge in the found shortest path.

Time complexity:

$$\begin{gathered} \mathrm{TC}=\mathrm{V}+\mathrm{VlogV}+\mathrm{E}+\mathrm{ElogV} \\ \mathrm{TC}=\mathrm{VlogV}+\mathrm{ElogV} \\ \mathrm{TC}=\mathrm{O}\left[\left(\mathrm{V}+\mathrm{E}\right)\mathrm{logV}\right] \end{gathered}$$

In the given question for finding the shortest path adjacent list and minheap both may use.

The time complexity is $\mathrm{TC}=\mathrm{O}\left[\left(\mathrm{V}+\mathrm{E}\right)\mathrm{logV}\right]$.