DP on a DAG: the Number of Paths and the Shortest Path
Lesson 10 of 17 · Graphs and trees
When a graph has no cycles, we can arrange the vertices topologically – so that all the edges go "forward". Then the shortest path, the longest path and the number of paths are calculated with one pass through the vertices, as in dynamic programming: the value of a vertex depends only on the vertices before it.
Before you start: prerequisites – topological sorting, introduction to DP. How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.
The idea
If the vertices are in a topological order, then at the moment the vertex v is processed, all the vertices from which v can be reached have already been processed. That is why we can "push" the value from v towards its neighbours:
Problem
Initial value
Transition for the edge v → u (weight w)
the number of paths from s
ways[s] = 1, the others 0
ways[u] += ways[v]
the shortest path from s
d[s] = 0, the others ∞
d[u] = min(d[u], d[v] + w)
the longest path from s
d[s] = 0, the others −∞
d[u] = max(d[u], d[v] + w)
Unlike Dijkstra, this also works with negative weights, and the longest path in a graph with cycles is a hard problem – in a DAG it is easy. The longest path is covered in detail in the lesson The longest path in a DAG.
The number of paths
The graph with the edges 1 → 2, 1 → 3, 2 → 3, 2 → 4, 3 → 4, 3 → 5 and 4 → 5. The input is n m and then m edges:
5 7
1 2
1 3
2 3
2 4
3 4
3 5
4 5
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long MOD = 1000000007;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n + 1);
vector<int> inDegree(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
inDegree[v]++;
}
// the topological order (Kahn)
vector<int> order;
queue<int> q;
for (int v = 1; v <= n; v++) if (inDegree[v] == 0) q.push(v);
while (!q.empty()) {
int v = q.front();
q.pop();
order.push_back(v);
for (int u : graph[v]) if (--inDegree[u] == 0) q.push(u);
}
// DP: ways[v] = the number of paths from 1 to v
vector<long long> ways(n + 1, 0);
ways[1] = 1;
for (int v : order)
for (int u : graph[v])
ways[u] = (ways[u] + ways[v]) % MOD;
cout << ways[n] << endl;
return 0;
}
In this example there are 5 paths from 1 to 5: 1-3-5, 1-2-3-5, 1-3-4-5, 1-2-3-4-5, 1-2-4-5, so the program prints 5. The number of paths grows exponentially, which is why it is calculated modulo 109+7.
The shortest path with negative weights
The input is n m and then m edges u v w; the program prints the shortest distance from vertex 1 to every vertex (or INF if the vertex cannot be reached).
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
const long long INF = 1e18;
int main() {
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> graph(n + 1);
vector<int> inDegree(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
inDegree[v]++;
}
vector<int> order;
queue<int> q;
for (int v = 1; v <= n; v++) if (inDegree[v] == 0) q.push(v);
while (!q.empty()) {
int v = q.front();
q.pop();
order.push_back(v);
for (auto [u, w] : graph[v]) if (--inDegree[u] == 0) q.push(u);
}
vector<long long> d(n + 1, INF);
d[1] = 0;
for (int v : order) {
if (d[v] == INF) continue; // v cannot be reached from 1
for (auto [u, w] : graph[v])
if (d[v] + w < d[u]) d[u] = d[v] + w;
}
for (int v = 1; v <= n; v++) cout << (d[v] == INF ? string("INF") : to_string(d[v])) << (v < n ? " " : "\n");
return 0;
}
Example
Input
5 7
1 2 2
1 3 6
2 3 -3
2 4 4
3 4 1
3 5 5
4 5 -2
Output
0 2 -1 0 -2
The complexity is O(n + m) – faster even than Dijkstra.
A grid is a DAG
The classic task "from the top-left to the bottom-right cell, moving only right and down" is DP on a DAG: the edges go only right and down, so there are no cycles, and the order "row by row, from left to right" is topological. That is why such tasks are solved with a double loop – see DP on a grid.
Practice tasks
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
TASK 01Difficulty: medium
Paths through a grid with obstacles
An n × m grid is given with the cells . (free) and # (an obstacle). How many paths are there from the top-left to the bottom-right cell, if you move only right and down? The answer modulo 109+7.
Example 1
Input
3 3
...
.#.
...
Output
2
Example 2
Input
2 2
.#
#.
Output
0
Hint
ways[i][j] = ways[i−1][j] + ways[i][j−1] for a free cell, 0 for an obstacle, and ways[0][0] = 1 if the starting cell is free. The row-by-row order is a topological order of this DAG.
Solution (C++)
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const long long MOD = 1000000007;
int main() {
int n, m;
cin >> n >> m;
vector<string> grid(n);
for (auto &r : grid) cin >> r;
vector<vector<long long>> ways(n, vector<long long>(m, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (grid[i][j] == '#') continue; // an obstacle: 0 paths
if (i == 0 && j == 0) { ways[i][j] = 1; continue; }
long long s = 0;
if (i > 0) s += ways[i - 1][j]; // came from above
if (j > 0) s += ways[i][j - 1]; // came from the left
ways[i][j] = s % MOD;
}
cout << ways[n - 1][m - 1] << endl;
return 0;
}
TASK 02Difficulty: medium
The cheapest journey
A city has n stations and m one-way lines u v c that always lead to a station with a larger number (u < v), with the price c (some lines have a discount, so c is negative). Print the lowest price of a journey from 1 to n, or NONE.
Example 1
Input
4 5
1 2 4
1 3 5
2 3 -3
2 4 2
3 4 -1
Output
0
Example 2
Input
3 1
1 2 5
Output
NONE
Hint
Since the edges go from a smaller number to a larger one, the order 1, 2, …, n is already topological – Kahn is not needed. Go through the vertices in order and relax the outgoing edges.
Solution (C++)
#include <iostream>
#include <vector>
using namespace std;
const long long INF = 1e18;
int main() {
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> graph(n + 1);
for (int i = 0; i < m; i++) {
int u, v, c;
cin >> u >> v >> c;
graph[u].push_back({v, c});
}
vector<long long> d(n + 1, INF);
d[1] = 0;
for (int v = 1; v <= n; v++) { // 1..n is a topological order
if (d[v] == INF) continue;
for (auto [u, c] : graph[v])
if (d[v] + c < d[u]) d[u] = d[v] + c;
}
if (d[n] == INF) cout << "NONE" << endl;
else cout << d[n] << endl;
return 0;
}
Common mistakes and tips
DP on a DAG works only if the graph has no cycle – check that Kahn has arranged all n vertices.
Do not relax from vertices that cannot be reached (the value ∞ or −∞).
Calculate the number of paths modulo and apply it immediately when adding.
Check your knowledge
Open the quiz
DP on a DAG
1. Why does DP on a DAG process the vertices in a topological order?
2. Does DP on a DAG work with negative weights?
3. How is the number of paths to the vertex u calculated?
Podešavanja kolačića
Koristimo kolačiće da bismo vam pružili najbolje moguće iskustvo. Takođe nam omogućavaju da analiziramo ponašanje korisnika kako bismo stalno poboljšavali veb lokaciju za vas.