Things to be discussed here,
- What is the shortest path, why do we even need to do this?
- How do we find the shortest path?
- What is the negative weight cycle?
So let us start out a discussion with an example. Imagine that you have a computer lab and want to have them all connected to the internet but you are in a tight budget, then what will you do? Yeah, and it is necessary to have them all connected to the internet.
Fig 1: All the nodes are computer and edges are wires
with weight ( length of wire required.)
In this situation, we will try to find the minimum cost to buy the cable required and to decrease the cost we need to decrease the cable length. So here we need to find the minimum length of cable length required to connect all the computers to the network.
The above is a simple example of the shortest path ( length of wire ) problem. More examples are
- Wire length optimization in the electronic circuits.
- Choosing the shortest route between two cities, etc.
Now let us describe it formally,
In 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 w(p) of path p = < v0, v1, v2, ... , vk > is the sum of the weights of its constituent edges.
w(p) = ∑ w(vi-1, vi) , 1 ≤ i ≤ k
We define shortest-path weight ∂(u,v) from u to v by
We define shortest-path weight ∂(u,v) from u to v by
- min( {w(p): u -> v } ) if there is a path from u to v
- ∞ otherwise
The shortest path from vertex u to vertex v is then defined as any path p with weight w(p) = ∂(u, v).
Note:
- Edge weights can represent metrics other than distances, such as time, cost, penalties, loss, or any other quantity that accumulates linearly along a path and that we would want to minimize.
- The BFS algorithm is a shortest-paths algorithm that works on unweighted graphs, that is, graphs in which each edge has unit weight.
Variants of Shortest Path Problems.
In this article, we shall focus on the single-source shortest-paths problem: given a graph G = (V, E), we want to find the shortest path from a given source vertex s belongs to V to each vertex v belongs to V. This can also solve these variants of problems.
In this article, we shall focus on the single-source shortest-paths problem: given a graph G = (V, E), we want to find the shortest path from a given source vertex s belongs to V to each vertex v belongs to V. This can also solve these variants of problems.
- Single-destination shortest-paths problem: Find the shortest path to a given destination vertex t from each vertex v. By reversing the direction of each edge in the graph, we can reduce this problem to a single-source problem.
- Singe pair shortest path problem: Find the shortest path from u to v for given vertices u and v.
- All-pair shortest-paths problem: Find the shortest path from u to v for every pair of vertices u and v.
Optimal Substructure of a Shortest Path
Shortest-paths algorithms typically rely on the property that the shortest path between two vertices contains other shortest path within it.
Lemma: ( Subpaths of shortest paths are shortest paths )
Given a weighted, directed graph G= (V, E) with weight function w: E->R, let p = < v0, v1, v2, ... , vk > be the shortest path from vertex v0 to vk and, for any i and j such that 0 ≤ i ≤ j ≤ k, let p = < vi, vi+1, ... , vj > be the subpath of p from vertex vi to vj. Then pij is the shortest path from vi to vj.
Negative-weight Edges
Some instances of the single source shortest-paths problems may include 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 belongs to V, the shortest path is well defined, even if it has a negative value.
If the graph contains 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 the shortest path as we can always find a path with lower weight by following the proposed "shortest" path and then traversing the negative-weight cycle. If there is a negative weight cycle on some path and then traversing the negative-weight cycle. If there is a negative weight cycle on some path from s to v, we define ∂(s,v) = -∞.
Okay, till now we have done a lot of theory part now we will be moving towards solving the problem-solving.
To solve the shortest path problem we have 3 algorithms these are
Here we will be just discussing the Bellman-ford algorithm and others will be discussed in the coming sessions. So let's start
The Bellman-Ford Algorithm
The Bellman-Ford algorithm finds the shortest paths from a starting node to all nodes of the graph. The algorithms can process all kinds of graphs, provided that the graph does not contain a cycle with a negative length. If the graph contains a negative cycle, the algorithm can detect this.
The algorithm keeps track of distances from the starting node to all nodes of the graph. Initially, the distance to all other nodes is infinite. The algorithm reduces the distances by finding edges that shorten the paths until it is not possible to reduce any distance. For a visual explanation please go through this video from Youtube.
Implementation
That's all for this article, in the next session we will be discussing Dijkstra Algorithm and problems related to it and for now practice problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).
If you have some content OR material related to this then do share them through the comment section for which we will be thankful to you.
Thank You
With 💙 by Learn DSA
Shortest-paths algorithms typically rely on the property that the shortest path between two vertices contains other shortest path within it.
Lemma: ( Subpaths of shortest paths are shortest paths )
Given a weighted, directed graph G= (V, E) with weight function w: E->R, let p = < v0, v1, v2, ... , vk > be the shortest path from vertex v0 to vk and, for any i and j such that 0 ≤ i ≤ j ≤ k, let p = < vi, vi+1, ... , vj > be the subpath of p from vertex vi to vj. Then pij is the shortest path from vi to vj.
Negative-weight Edges
Some instances of the single source shortest-paths problems may include 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 belongs to V, the shortest path is well defined, even if it has a negative value.
If the graph contains 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 the shortest path as we can always find a path with lower weight by following the proposed "shortest" path and then traversing the negative-weight cycle. If there is a negative weight cycle on some path and then traversing the negative-weight cycle. If there is a negative weight cycle on some path from s to v, we define ∂(s,v) = -∞.
Okay, till now we have done a lot of theory part now we will be moving towards solving the problem-solving.
To solve the shortest path problem we have 3 algorithms these are
- The Bellman-Ford algorithm
- Dijkstra algorithm
- Floyd-Warshall's algorithm.
Here we will be just discussing the Bellman-ford algorithm and others will be discussed in the coming sessions. So let's start
The Bellman-Ford Algorithm
The Bellman-Ford algorithm finds the shortest paths from a starting node to all nodes of the graph. The algorithms can process all kinds of graphs, provided that the graph does not contain a cycle with a negative length. If the graph contains a negative cycle, the algorithm can detect this.
The algorithm keeps track of distances from the starting node to all nodes of the graph. Initially, the distance to all other nodes is infinite. The algorithm reduces the distances by finding edges that shorten the paths until it is not possible to reduce any distance. For a visual explanation please go through this video from Youtube.
Implementation
- Store the graph in an edge list edges that consists of tuples of the form ( a, b, w), meaning that there is an edge from node a to node b with weight w.
- The algorithm consists of n-1 rounds, and in each round, the algorithm iterates through all edges of the graph and tries to reduce the distances. The algorithm constructs an array distance that will contain the distances from x to all nodes of the graph.
- The running time of the algorithm is O(n.m) where n-number of nodes, and m-number of edges.
- If there are no negative cycles in the graph, all distances are final after n-1 rounds, because each shortest path can contain at most n-1 edges.
Fig 2: Example Graph
Application of Bellman-Ford Algorithm
- It is used to check if the graph contains a cycle with a negative length.
- If the graph contains a negative cycle then we can shorten infinitely many times.
- The negative cycle can be detected by running the Bellman-Ford algorithm for n rounds.
- n-1 round to get the shortest distance.
- copy the previous distance to another array and run the Bellman-Ford for one more round in this array.
- Check for distances in both array, if both are same then no negative cycle else there is a negative cycle.
Practice Problem
That's all for this article, in the next session we will be discussing Dijkstra Algorithm and problems related to it and for now practice problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).
If you have some content OR material related to this then do share them through the comment section for which we will be thankful to you.
Thank You
With 💙 by Learn DSA