Question

You are given a directed graph with (possibly negative) weighted edges, in which the shortest path between any two vertices is guaranteed to have at most edges. Give an algorithm that finds the shortest path between two vertices u and v in $\mathbf{O}\left(K\left|E\right|\right)$time.

Short answer

Bellman Ford algorithm in which the edges have negative weights and it finds the shortest path between two vertices in$O\left(K\left|E\right|\right)$ time.

Step-by-step solution

 Step 1: Algorithm used for negative weighted directed graph

Bellman-Ford algorithmis an application of a 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 works only for the graph with a positive weight and Bellman-Ford algorithm works with graphs in which edges have negative weights in its graph.

Design the Algorithm

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 time at most$O\left(K\left|E\right|\right)$ So, here the vertex A is the source vertex. Now take an array as a data structure to evaluate a single source’s 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. Draw a directed positive and negative weighted graph as shown below:

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 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 the vertex A to vertex D is evaluate in $O\left(K\left|E\right|\right)$time.