图中最短路径的数量 | Baeldung中文网

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 of nodes numbered from to . In addition, we have edges that connect these nodes. We’re given two numbers and 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 to the destination .

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

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 to node we have paths:

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

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

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:

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

Initially, the distance value for all nodes is infinity except the source node equal to (length of the shortest path from a node to itself always equal to $\boldsymbol{0}$ ). Also, the paths value for all nodes is except the source node equal to (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 value for the child node will be updated to be equal to the 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 with its . So, we’ll keep the distance value of the child node the same. However, we’ll increase the value of the child node by the value of the current node.

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

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:

: where represents the length of the shortest path that goes from the source node to the node .
: where represents the number of shortest paths from the source node to the node .

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 is the number of nodes and 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:

: representing the length of the path we took from the source node to the current one.
: 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:

: where represents the length of the shortest paths from the source node to the node .
: where represents the number of shortest paths from the source node to the node .

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 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 value for the child node will be updated to be equal to the 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 value of the child node by the 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 is the number of nodes and 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.

Persistence

REST

Security