求解有向无环图两点间所有路径c#实现

有向无环图（DAG）是一种特殊的有向图，其中不存在环，即不存在从一个节点出发沿着有向边走可以回到该节点的情况。在DAG中，从一个节点到另一个节点可能有多条路径。

求解DAG两点间的所有路径c，可以使用动态规划算法。假设有两个节点A和B，分别为起点和终点。设c(i,j)表示从节点i到节点j的所有路径长度之和。则有：

c(i,j) = 0 当i = j时

c(i,j) = ∑[c(i,k) × w(k,j)] 当存在从节点i到节点j的有向边(i, j)时

其中，k为i节点的后继节点，w(k,j)为(i, j)边的权重。

利用上述公式，我们可以递归的求解所有的c(i,j)，并得到从节点A到节点B的所有路径长度之和。

除此之外，可以使用拓扑排序算法对DAG进行排序，然后按照拓扑序依次计算每对节点之间的路径长度和。这样可以保证节点的前驱节点已经被计算过，避免了重复计算。

相关问题

设计算法求解有向无环图的所有拓扑序列。

求解有向无环图的所有拓扑序列可以使用回溯算法，具体步骤如下：

1. 统计每个顶点的入度，将入度为 0 的顶点加入队列中。

2. 对于队列中的每个顶点，依次移除该顶点，并将该顶点的所有邻接点的入度减 1。

3. 递归处理剩余的顶点，直到所有顶点都被移除。

4. 如果某个顶点的入度不为 0，说明该顶点无法被移除，回溯上一层继续处理。

5. 如果所有顶点都被移除，并且没有回溯，则找到了一个拓扑序列。将该序列保存，并回溯上一层继续寻找其他序列。

6. 对于每个节点，需要保存它的出度节点，以便在移除该节点时更新其邻接点的入度。

下面是 Python 实现代码：

def all_topological_sorts(graph):
    # 统计每个节点的入度
    in_degree = {v: 0 for v in graph}
    for v in graph:
        for w in graph[v]:
            in_degree[w] += 1

    # 将入度为 0 的节点加入队列
    queue = [v for v in in_degree if in_degree[v] == 0]

    # 寻找所有拓扑序列
    def backtrack(path):
        if len(path) == len(graph):
            yield path
            return
        for v in queue:
            if v not in path:
                new_path = path + [v]
                new_queue = queue.copy()
                new_queue.remove(v)
                for w in graph[v]:
                    in_degree[w] -= 1
                    if in_degree[w] == 0:
                        new_queue.append(w)
                yield from backtrack(new_path)
                for w in graph[v]:
                    in_degree[w] += 1
                new_queue.append(v)

    return list(backtrack([]))

其中，`graph` 是一个字典，表示有向无环图，字典的键为节点，值为该节点的出度节点列表。函数返回所有可能的拓扑序列列表。

算法题：C++求有向无环图的路径数

有向无环图的路径数可以通过拓扑排序和动态规划求解。

假设该有向无环图有 $n$ 个节点，$m$ 条边，$inDegree[i]$ 表示节点 $i$ 的入度，$dp[i]$ 表示从起点到节点 $i$ 的路径总数，则可以按照如下步骤求解：

1. 初始化：将所有入度为 0 的节点的 $dp$ 值赋为 1。

2. 拓扑排序：从入度为 0 的节点开始，依次遍历其出边指向的节点，将这些节点的入度减 1。如果减为 0，则将其加入拓扑序列中。重复该过程直至所有节点都被遍历。

3. 动态规划：按照拓扑序列的顺序，依次更新每个节点的 $dp$ 值。对于每个节点 $i$，遍历其所有入边指向的节点 $j$，将 $dp[j]$ 加到 $dp[i]$ 中。

4. 输出结果：最终 $dp$ 数组中，终点的值即为从起点到终点的路径总数。

以下是 C++ 代码实现：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int inDegree[N], dp[N];
vector<int> edges[N];

void topoSort()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!inDegree[i])
            q.push(i), dp[i] = 1;

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto v : edges[u])
        {
            inDegree[v]--;
            if (!inDegree[v])
                q.push(v);
            dp[v] += dp[u];
        }
    }
}

int main()
{
    cin >> n >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);
        inDegree[b]++;
    }

    topoSort();

    cout << dp[n] << endl;

    return 0;
}