Number of Shortest Paths in a Graph | Baeldung on Computer Science

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$ :

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

$1 \rightarrow 2 \rightarrow 4$ , with length equal to $2$ .
$1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ , with length equal to $3$ .
$1 \rightarrow 3 \rightarrow 4$ , with length equal to $2$ .
$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:

algorithm BFSApproachForUnweightedGraphs(V, G, S, D):
    // INPUT
    //     V = the number of nodes in the graph
    //     G = the graph stored as an adjacency list
    //     S = the index of the source node
    //     D = the index of the destination node
    // OUTPUT
    //     Returns the number of shortest paths between S and D

    distance <- map[v : infinity | v in V]
    paths <- map[v : 0 | v in V]
    queue <- create an empty queue
    queue.add(S)
    distance[S] <- 0
    paths[S] <- 1

    while queue is not empty:
        current <- queue.front()
        queue.pop()
        for child in G[current]:
            if visited[child] = false:
                queue.add(child)
                visited[child] <- true
            if distance[child] > distance[current] + 1:
                distance[child] <- distance[current] + 1
                paths[child] <- paths[current]
            else if distance[child] = distance[current] + 1:
                paths[child] <- paths[child] + paths[current]

    return paths[D]

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:

algorithm DijkstrasApproachForWeightedGraphs(G, S, D):
    // INPUT
    //     V = the number of nodes in the graph
    //     G = the graph stored as an adjacency list
    //     S = the index of the source node
    //     D = the index of the destination node
    // OUTPUT
    //     Returns the number of shortest paths between S and D

    distance <- [n in V | infinity]
    paths <- [n in V | 0]
    priority_queue <- create an empty priority queue
    priority_queue.add({0, S})
    distance[S] <- 0
    paths[S] <- 1

    while priority_queue is not empty:
        current <- priority_queue.front().node
        length <- priority_queue.front().length
        priority_queue.pop()
    
        for edge in G[current]:
            node <- edge.node
            cost <- edge.cost
            
            if distance[node] > distance[current] + cost:
                priority_queue.add((length + cost, node))
                distance[node] <- distance[current] + cost
                paths[node] <- paths[current]
            else if distance[node] = distance[current] + cost:
                paths[node] <- paths[node] + paths[current]

    return paths[D]

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.

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex

Full Archive

About Baeldung