Guide to Competitive Programming

Finding a shortest path between two nodes of a graph is an important problem that has many practical applications.

For example, a natural problem related to a road network is to calculate the shortest possible length of a route between two cities, given the lengths of the roads.

In an unweighted graph, the length of a path equals the number of its edges, and we can simply use breadth-first search to find a shortest path. However, in this section we focus on weighted graphs where more sophisticated algorithms are needed for finding shortest paths.

Bellman–Ford algorithm

Bellman–Ford Algorithm:

The Bellman–Ford algorithm finds shortest paths from a starting node to all nodes of the graph. The algorithm can process all kinds of graphs, provided that the graph does not contain a cycle with 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 the starting node is 0 and the distance to any other node is infinite. The algorithm then reduces the distances by finding edges that shorten the paths until it is not possible to reduce any distance.

Shows how the Bellman–Ford algorithm processes a graph. First, the algorithm reduces distances using the edges 1 → 2, 1 → 3 and 1 → 4, then using the edges 2 → 5 and 3 → 4, and finally using the edge 4 → 5. After this, no edge
can be used to reduce distances, which means that the distances are final.

Implementation The implementation of the Bellman–Ford algorithm below determines the shortest distances from a node x to all nodes of the graph. The code assumes that the graph is stored as 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 on each round the algorithm goes through all edges of the graph and attempts to reduce the distances. The algorithm constructs an array distance that will contain the distances from node x to all nodes. The constant INF denotes an infinite distance.

graph negative cycle

for (int i = 1; i <= n; i++) {
distance[i] = INF;
}
distance[x] = 0;
for (int i = 1; i <= n-1; i++) {
for (auto e : edges) {
int a, b, w;
tie(a, b, w) = e;
distance[b] = min(distance[b], distance[a]+w);
}
}

The time complexity of the algorithm is O(nm), because the algorithm consists of n−1 rounds and iterates through all m edges during a round. 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.

There are several ways to optimize the algorithm in practice. First, the final distances can usually be found earlier than after n−1 rounds, so we can simply stop the algorithm if no distance can be reduced during a round. A more advanced variant is the SPFA algorithm (“Shortest Path Faster Algorithm” [8]) which maintains a queue of nodes that might be used for reducing the distances. Only the nodes in the queue will be processed, which often yields a more efficient search.

Negative Cycles The Bellman–Ford algorithm can also be used to check if the graph contains a cycle with negative length. In this case, any path that contains the cycle can be shortened infinitely many times, so the concept of a shortest path is not meaningful.

For example, the graph contains a negative cycle 2 → 3 → 4 → 2 with length −4.

A negative cycle can be detected using the Bellman–Ford algorithm by running the algorithm for n rounds. If the last round reduces any distance, the graph contains a negative cycle. Note that this algorithm can be used to search for a negative cycle in the entire graph regardless of the starting node.

Dijkstra’s Algorithm:

Dijkstra’s algorithm finds shortest paths from the starting node to all nodes of the graph, like the Bellman–Ford algorithm. The benefit of Dijkstra’s algorithm is that it is more efficient and can be used for processing large graphs.

However, the algorithm requires that there are no negative weight edges in the graph.

Dijkstra algorithm

Like the Bellman–Ford algorithm, Dijkstra’s algorithm maintains distances to the nodes and reduces them during the search. At each step, Dijkstra’s algorithm selects a node that has not been processed yet and whose distance is as small as possible.

Then, the algorithm goes through all edges that start at the node and reduces the distances using them. Dijkstra’s algorithm is efficient, because it only processes each edge in the graph once, using the fact that there are no negative edges.

Shows how Dijkstra’s algorithm processes a graph. Like in the Bellman–Ford algorithm, the initial distance to all nodes, except for the starting node, is infinite. The algorithm processes the nodes in the order 1, 5, 4, 2, 3, and at
each node reduces distances using edges that start at the node. Note that the distance to a node never changes after processing the node.

Implementation An efficient implementation of Dijkstra’s algorithm requires that we can efficiently find the minimum-distance node that has not been processed. An appropriate data structure for this is a priority queue that contains the remaining nodes ordered by their distances. Using a priority queue, the next node to be processed can
be retrieved in logarithmic time.

A typical textbook implementation of Dijkstra’s algorithm uses a priority queue
that has an operation for modifying a value in the queue. This allows us to have a single instance of each node in the queue and update its distance when needed.

However, standard library priority queues do not provide such an operation, and a somewhat different implementation is usually used in competitive programming.

The idea is to add a new instance of a node to the priority queue always when its distance changes.

Our implementation of Dijkstra’s algorithm calculates the minimum distances from a node x to all other nodes of the graph. The graph is stored as adjacency lists so that adj[a] contains a pair (b, w) always when there is an edge from node a to node b with weight w. The priority queue

priority_queue<pair<int,int>> q;

contains pairs of the form (−d, x), meaning that the current distance to node x is d.

The array distance contains the distance to each node, and the array processed indicates whether a node has been processed.
Note that the priority queue contains negative distances to nodes. The reason for this is that the default version of the C++ priority queue finds maximum elements, while we want to find minimum elements. By exploiting negative distances, we can directly use the default priority queue.2 Also note that while there may be several instances of a node in the priority queue, only the instance with the minimum distance will be processed.

The implementation is as follows:

for (int i = 1; i <= n; i++) {
distance[i] = INF;
}
distance[x] = 0;
q.push({0,x});
while (!q.empty()) {
int a = q.top().second; q.pop();
if (processed[a]) continue;
processed[a] = true;
for (auto u : adj[a]) {
int b = u.first, w = u.second;
if (distance[a]+w < distance[b]) {
distance[b] = distance[a]+w;
q.push({-distance[b],b});
}
}
}

The time complexity of the above implementation is O(n + m logm), because the algorithm goes through all nodes of the graph and adds for each edge at most one distance to the priority queue.

Negative Edges The efficiency of Dijkstra’s algorithm is based on the fact that the graph does not have negative edges. However, if the graph has a negative edge, the 2Of course, we could also declare the priority queue as in Sect. 5.2.3 and use positive distances, but the implementation would be longer.

Dijkstras algorithm

Algorithm may give incorrect results. As an example, consider the graph in the shortest path from node 1 to node 4 is 1 → 3 → 4 and its length is 1. However, Dijkstra’s algorithm incorrectly finds the path 1 → 2 → 4 by greedily following minimum weight edges.

Floyd–Warshall Algorithm:

The Floyd–Warshall algorithm provides an alternative way to approach the problem of finding shortest paths. Unlike the other algorithms in this chapter, it finds shortest paths between all node pairs of the graph in a single run.
The algorithm maintains a matrix that contains distances between the nodes. The initial matrix is directly constructed based on the adjacency matrix of the graph.

Then, the algorithm consists of consecutive rounds, and on each round, it selects a new node that can act as an intermediate node in paths from now on, and reduces distances using this node.

Let us simulate the Floyd–Warshall algorithm for the graph. In this case, the initial matrix is as follows:

Warshall algorithm

On the first round, node 1 is the new intermediate node. There is a new path between nodes 2 and 4 with length 14, because node 1 connects them. There is also a new path between nodes 2 and 5 with length 6.

Floyd–Warshall algorithm

Shortest Paths- Competitive programming

On the second round, node 2 is the new intermediate node. This creates new paths between nodes 1 and 3 and between nodes 3 and 5:

shortest path

The algorithm continues like this, until all nodes have been appointed intermediate nodes. After the algorithm has finished, the matrix contains the minimum distances between any two nodes:

Shortest-Paths-Competitive-programming

For example, the matrix tells us that the shortest distance between nodes 2 and 4 is 8. This corresponds to the path.

Implementation The Floyd–Warshall algorithm is particularly easy to implement.

The implementation below constructs a distance matrix where dist[a][b] denotes the shortest distance between nodes a and b. First, the algorithm initializes dist using the adjacency matrix adj of the graph:

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) dist[i][j] = 0;
else if (adj[i][j]) dist[i][j] = adj[i][j];
else dist[i][j] = INF;
}
}

After this, the shortest distances can be found as follows:

topological sort

for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}

The time complexity of the algorithm is O(n3), because it contains three nested loops that go through the nodes of the graph.
Since the implementation of the Floyd–Warshall algorithm is simple, the algorithm can be a good choice even if it is only needed to find a single shortest path in the graph. However, the algorithm can only be used when the graph is so small that a cubic time complexity is fast enough.