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:

ProblemInitial valueTransition for the edge v → u (weight w)
the number of paths from sways[s] = 1, the others 0ways[u] += ways[v]
the shortest path from sd[s] = 0, the others ∞d[u] = min(d[u], d[v] + w)
the longest path from sd[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
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
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?