Question

You are given a set of cities, along with the pattern of highways between them, in the form of an undirected graph G = (V , E). Each stretch of highway $\mathit{e}\mathbf{\in }\mathit{E}$connects two cities, and you know its length in miles, le. You want to get from city s to city t. There’s one problem: your car can only hold enough gas to cover L miles. There are gas stations in each city, but not between cities. Therefore, you can only take a route if every one of its edges has length ${\mathbf{l}}_{\mathbf{e}}\mathbf{\le }\mathbf{L}$

(a) Given the limitation on your car’s fuel tank capacity, show how to determine in linear time whether there is a feasible route from sto t.

(b) You are now planning to buy a new car, and you want to know the minimum fuel tank capacity that is needed to travel from s to t. Give an$\mathbf{O}\mathbf{\left[}\left(\left|V\right|+\left|E\right|\right)\mathbf{log}\left|V\right|\mathbf{\right]}$algorithm to determine this.

Short answer

a). The feasible route or the shortest route from s to t is evaluate by using Dijkstra algorithm and by using depth first search.

b) $\mathrm{TC}=\mathrm{O}\left[\left(\mathrm{V}+\mathrm{E}\right)\mathrm{logV}\right]$time complexity is performed by the Dijkstra’salgorithm.

Step-by-step solution

Dijkstra’s Algorithm and Depth First search

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.

Determine the feasible route from s to t.

(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

Step 3: Dijkstra’salgorithm performs TC=O[V+ElogV] time complexity.

(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]$.