Introduction to Single Source Shortest path and it's types in ADA

I am going to introduce a concept through which we can calculate the shortest distance of all the destination vertices form the single source. In this topic, we will see different types of weights (positive and negative) on edges in a graph and there may be chances to get the negative weight edges/cycles in G->(V,E). Then we will see, whether we can find out the shortest path or fall into the infinity loop.

All cases are going to be discussed  in this topic with diagrammatic and real  approach




A motorist wishes to find the shortest possible route from Chicago to Boston. Given a road map of the United States on which the distance between each pair of adjacent intersections is marked, how can we determine this shortest route?

One possible way is to enumerate all the routes from Chicago to Boston, add up the distances on each route, and select the shortest. It is easy to see, however, that even if we disallow routes that contain cycles, there are millions of possibilities, most of which are simply not worth considering. For example, a route from Chicago to Houston to Boston is obviously a poor choice, because Houston is about a thousand miles out of the way.

We show how to solve such problems efficiently. In a shortest-paths problem, we are given a weighted, directed graph G = (V, E), with weight function w: E → R mapping edges to real-valued-weights. The weight of path p = 〈v₀, v₁…., v_k〉 is the sum of the weights of its constituent edges:

Edge weights can be interpreted as metrics other than distances. They are often used to represent time, cost, penalties, loss, or any other quantity that accumulates linearly along a path and that one wishes to minimize

 

Negative-weight edges

In some instances of the single-source shortest-paths problem, there may be edges whose weights are negative. If the graph G = (V, E) contains no negative-weight cycles reachable from the source s, then for all v ∈ V, the shortest-path weight δ(s, v) remains well defined.

Even if it has a negative value. If there is a negative-weight cycle reachable from s, however, shortest-path weights are not well defined. No path from s to a vertex on the cycle can be a shortest path-a lesser-weight path can always be found that follows the proposed "shortest" path and then traverses the negative-weight cycle. If there is a negative-weight cycle on some path from s to v, we define δ(s, v) = -∞.

Illustrates the effect of negative weights and negative-weight cycles on shortest-path weights.

Because there is only one path from s to a (the path 〈s, a〉), δ(s, a) = w(s, a) = 3. Similarly, there is only one path from s to b, and so δ(s, b) = w(s, a) + w(a, b) = 3 + (-4) = -1. 

There are infinitely many paths from s to c: 〈s, c〉, 〈s, c, d, c〉, 〈s, c, d, c, d, c〉, and so on. Because the cycle 〈c, d, c〉 has weight 6 + (-3) = 3 > 0, the shortest path from s to c is 〈s, c〉, with weight δ(s, c) = 5. 

Similarly, the shortest path from s to d is 〈s, c, d〉, with weight δ(s, d) = w(s, c) + w(c, d) = 11.

Analogously, there are infinitely many paths from s to e: 〈s, e〉, 〈s, e, f, e〉, 〈s, e, f, e, f, e〉, and so on. Since the cycle 〈e, f, e〉 has weight 3 + (-6) = -3 < 0, however, there is no shortest path from s to e.

 By traversing the negative-weight cycle 〈e, f, e〉 arbitrarily many times, we can find paths from s to e with arbitrarily large negative weights, and so δ(s, e) = -∞. Similarly, δ(s, f) = -∞. 

Because g is reachable from f, we can also find paths with arbitrarily large negative weights from s to g, and δ(s, g) = -∞. Vertices h, i, and j also form a negative-weight cycle. They are not reachable from s, however, and so δ(s, h) = δ(s, i) = δ(s, j) = ∞.

Some shortest-paths algorithms, such as Dijkstra's algorithm, assume that all edge weights in the input graph are nonnegative, as in the road-map example. Others, such as the Bellman-Ford algorithm, allow negative-weight edges in the input graph and produce a correct answer as long as no negative-weight cycles are reachable from the source. Typically, if there is such a negative-weight cycle, the algorithm can detect and report its existence.

Properties of shortest paths and relaxation

Triangle inequality

• For any edge (u, v) ∈ E, we have δ(s, v) ≤ δ(s, u) + w(u, v).

Upper-bound property

·         We always have d[v] ≥ δ(s, v) for all vertices v ∈ V , and once d[v] achieves the value δ(s, v), it never changes.

No-path property

·         If there is no path from s to v, then we always have d[v] = δ(s, v) = ∞.

Convergence property

If s->u->v is a shortest path in G for some u, v ∈ V, and if d[u] = δ(s, u) at any time prior to relaxing edge (u, v), then d[v] = δ(s, v) at all times afterward

Dijkstra's algorithm

Dijkstra's algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (V, E) for the case in which all edge weights are nonnegative. In this section, therefore, we assume that w(u, v) ≥ 0 for each edge (u, v) ∈ E. As we shall see, with a good implementation, the running time of Dijkstra's algorithm is lower than that of the Bellman-Ford algorithm.

Dijkstra's algorithm maintains a set S of vertices whose final shortest-path weights from the source s have already been determined. The algorithm repeatedly selects the vertex u ∈ V - S with the minimum shortest-path estimate, adds u to S, and relaxes all edges leaving u. In the following implementation, we use a min-priority queue Q of vertices, keyed by their d values

The Bellman-Ford algorithm

The Bellman-Ford algorithm solves the single-source shortest-paths problem in the general case in which edge weights may be negative. Given a weighted, directed graph G = (V, E) with source s and weight function w : E → R, the Bellman-Ford algorithm returns a boolean value indicating whether or not there is a negative-weight cycle that is reachable from the source. If there is such a cycle, the algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces the shortest paths and their weights.

The algorithm uses relaxation, progressively decreasing an estimate d[v] on the weight of a shortest path from the source s to each vertex v ∈ V until it achieves the actual shortest-path weight δ(s, v). The algorithm returns TRUE if and only if the graph contains no negative-weight cycles that are reachable from the source.