Question

You are given a directed graph $\mathbf{G}\left(V,E\right)$with (possibly negative) weighted edges, along with a specific node $\mathbf{s}\mathbf{\in }\mathbf{V}$and a tree $\mathbf{T}\mathbf{=}\left(V,E\text{'}\right)\mathbf{,}\mathbf{E}\mathbf{\text{'}}\underline{\mathbf{\subset }}\mathbf{E}$. Give an algorithm that checks whether T is a shortest-path tree for G with starting point s . Your algorithm should run in linear time.

Short answer

The algorithm to check whether T is a shortest-path tree for G with starting point s is explained, which runs in a linear time.

Step-by-step solution

Algorithm used for negative weighted directed graph.

Bellman Ford algorithmis an application of single source shortest path, which is used forfinding the shortest distance from one vertex to other vertices of a weighted directed graph.

It is almost similar to Dijkstra's algorithm but Dijkstra's algorithm is works only for the graph with a positive weight and Bellman Ford algorithm is works with graphs in which edges have negative weights in its graph.

Design the Algorithm .T=(V,E'),E'⊂E

Bellman-Ford algorithm applies to the graph for finding the single source’s shortest path.A directed graph with positive and negative edge weight, and returns the length of the shortest cycle in the graph and the graph is acyclic, which takes linear time. So, here the vertex A is the source vertex. now take an array as a data structure to evaluate single source shortest path between the source and the destination.

From A the distance of A is zero and take the distance of vertex A from each and every vertex is infinity. Now take A as the first vertex and evaluate the weight towards each vertex and draw a directed positive and negative weighted graph:

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 the vertex arises.

Here 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 A is zero and take the distance of vertex A from each and every vertex is infinity.

All vertices will be released many times in the Bellman-Ford algorithm.

Select every vertex one by one and put it into the array as a data structure one by one as shown in the figure.

Hence, the shortest distance from vertex A to vertex D is evaluated in linear time