1. Overview

In this tutorial, we’ll discuss the problem of counting the number of shortest paths between two nodes in a graph. Firstly, we’ll define the problem and provide an example that explains it.

Secondly, we’ll discuss two approaches to this problem. The first one is for unweighted graphs, while the other approach is for weighted ones.

2. Defining the Problem

Suppose we have a graph G of V nodes numbered from 1 to V. In addition, we have E edges that connect these nodes. We’re given two numbers S and D that represent the source node’s indices and the destination node, respectively.

Our task is to count the number of shortest paths from the source node S to the destination D.

Recall that the shortest path between two nodes A and B is the path that has the minimum length among all possible paths between A and B.

Let’s check an example for better understanding. Suppose we have the following graph and we’re given S = 1 and D = 4:

Graph Example 1

To go from node S to node D we have 4 paths:

  1. 1 \rightarrow 2 \rightarrow 4, with length equal to 2.
  2. 1 \rightarrow 2 \rightarrow 3 \rightarrow 4, with length equal to 3.
  3. 1 \rightarrow 3 \rightarrow 4, with length equal to 2.
  4. 1 \rightarrow 3 \rightarrow 2 \rightarrow 4, with length equal to 3.

As we can see, the shortest path has a length equal to 2. Also, we notice that we have two paths having a length equal to 2. Therefore, there are 2 shortest paths between node S and node D.

3. Unweighted Graphs

3.1. Main Idea

The main idea here is to use BFS (Breadth-First Search) to get the source node’s shortest paths to every other node inside the graph. We’ll store for every node two values:

  • distance: representing the length of the shortest path from the source to the current one.
  • paths: representing the number of these shortest paths.

Initially, the distance value for all nodes is infinity except the source node equal to 0 (length of the shortest path from a node to itself always equal to \boldsymbol{0}). Also, the paths value for all nodes is 0 except the source node equal to 1 (a node has a single shortest path to itself).

Next, we start traversing the graph using the BFS algorithm. Each time when we want to add a child of the current node to the queue, we’ll have two choices:

  • If \boldsymbol{ distance [child] > distance[current] + 1 }, that means there is a path that goes from the source node to the child node with a smaller length than the previous path we have. So, we’ll minimize the child node’s distance value to be equal to the current node distance plus one. In addition, the paths value for the child node will be updated to be equal to the paths value of the current node.
  • If \boldsymbol{ distance [child] = distance [current] + 1 }, that means all the shortest paths that go from the source node to the current node will be added to the number of shortest paths of the child node. The reason is that they will have the same length as the shortest path of the child node after adding the edge that connects current with its child. So, we’ll keep the distance value of the child node the same. However, we’ll increase the paths value of the child node by the paths value of the current node.

Finally, the paths value of the D node will have the number of shortest paths that go from the source node S to the destination node D. Also, the distance value of the D node will have the length of the shortest path that goes from S to D.

3.2. Implementation

Let’s take a look at the implementation:

Rendered by QuickLaTeX.com

Initially, we declare two arrays:

  • distance: where distance[u] represents the length of the shortest path that goes from the source node to the node u.
  • paths: where paths[u] represents the number of shortest paths from the source node to the node u.

We also declared an empty queue to store nodes during BFS traversal.

Next, we perform multiple steps as long as the queue isn’t empty. In each step, we take the current node positioned in the front of the queue and iterate over its children. For each child, we check whether we haven’t visited that child node before. If so, we add it to the queue and mark it as a visited node. Also, we update the distance and paths value for the child node based on the rules mentioned in section 3.1.

Finally, we return paths[D] which stores the number of shortest paths that go from the source node to the destination.

The complexity of this approach is the same as the BFS complexity, which is \boldsymbol{ O(V + E) }, where V is the number of nodes and E is the number of edges. The reason behind this complexity is that we iterate over each node only once. Therefore, we iterate over its children once. In total, we iterate over each edge once as well.

4. Weighted Graphs

4.1. Main Idea

We’ll apply the same concepts from the BFS Approach to solve the same problem for weighted graphs. However, to get the shortest path in a weighted graph, we have to guarantee that the node that is positioned at the front of the queue has the minimum distance-value among all the other nodes that currently still in the queue. So, we’ll use Dijkstra’s algorithm.

In Dijkstra’s algorithm, we declare a priority queue that stores a pair of values:

  • length: representing the length of the path we took from the source node to the current one.
  • node: representing the current node itself.

We’ll set the priority of our queue to give us the node with the minimal length to get the shortest path from the source node to the current node.

Finally, the remaining workflow will still the same as the BFS Approach.

4.2. Implementation

Let’s take a look at the implementation:

Rendered by QuickLaTeX.com

Initially, we declare the same two arrays from the previous approach:

  • distance: where distance[u] represents the length of the shortest paths from the source node to the node u.
  • paths: where paths[u] represents the number of shortest paths from the source node to the node u.

We also declare an empty priority queue to store the explored nodes and sorted them in acceding order according to their distance value.

Next, we perform similar steps to the ones in unweighted graphs. As long as the priority queue isn’t empty, we pop the current node positioned in the front of the priority queue with its length (length of the path we took from the source node to the current node).

After that, we iterate over the children of the current node. For each child, we check whether it has a distance value greater than the current node’s distance value plus the cost of the current-child edge. If so, we add this child to the priority queue. Also, we update the distance value and paths value for the child node.

In the case of weighted graphs, the next steps are tweaked a little:

  • If \boldsymbol{ distance [child] > distance [current] + cost }, we minimize the distance value of the child node to be equal to the current node distance plus the cost of the current-child edge. In addition, the paths value for the child node will be updated to be equal to the paths value of the current node.
  • If \boldsymbol{ distance [child] = distance [current] + cost }, we keep the distance value of the child node the same. Also, we increase the paths value of the child node by the paths value of the current node.

Finally, we return paths [D] which store the number of shortest paths that go from the source node to the destination node.

The complexity here is the same as the Dijkstra complexity, which is \boldsymbol{ O(E + V \times log(V)) }, where V is the number of nodes and E is the number of edges. The reason is similar to the BFS approach. Since we iterate over each edge once and the priority queue needs O(log(V)) complexity to add each node, then V \times log(V) is the time complexity to keep all the nodes in the priority queue sorted by their length value.

5. Conclusion

In this tutorial, we presented the problem of counting the number of shortest paths between two nodes in a graph. We explained the general idea and discussed two approaches for the weighted and unweighted graphs.

2 Comments
Oldest
Newest
Inline Feedbacks
View all comments
Comments are closed on this article!