Suppose G be a weighted directed graph where a minimum labeled w(u, v) associated with each edge (u, v) in E, called weight of edge (u, v). These weights represent the cost to traverse the edge. A path from vertex u to vertex v is a sequence of one or more edges.
<(v1,v2), (v2,v3), . . . , (vn-1, vn)> in E[G] where u = v1 and v = vn
The cost (or length or weight) of the path P is the sum of the weights of edges in the sequence.
The shortest-path weight from a vertex uÎV to a vertex vÎV in the weighted graph is the minimum cost of all paths from u to v. If there exists no such path from vertex u to vertex v then the weight of the shortest-path is ∞.
The negative weight cycle is a cycle whose total is negative. No path from starting vertex S to a vertex on the cycle can be a shortest path. Since a path can run around the cycle many, many times and get any negative cost desired. in other words, a negative cycle invalidates the noton of distance based on edge weights.
This technique consists of testing whether we can improve the shortest path found so far if so update the shortest path. A relaxation step may or may not decrease the value of the shortest-path estimate.
The following code performs a relaxation step on edge(u,v).
Relax (u, v, w)
If d[u] + w(u, v) < d[v]
then d[v] d[u] + w[u, v]
Given a weighted graph G, find a shortest path from given vertex to each other vertex in G. Note that we can solve this problem quite easily with BFS traversal algorithm in the special case when all weights are 1. The greedy approach to this problem is repeatedly selecting the best choice from those available at that time.